New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

Intro to Discrete Structures

by: Mrs. Dangelo Fahey

Intro to Discrete Structures MATH 1165

Mrs. Dangelo Fahey
GPA 3.73


Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Class Notes
25 ?




Popular in Course

Popular in Mathematics (M)

This 4 page Class Notes was uploaded by Mrs. Dangelo Fahey on Sunday October 25, 2015. The Class Notes belongs to MATH 1165 at University of North Carolina - Charlotte taught by Staff in Fall. Since its upload, it has received 19 views. For similar materials see /class/228918/math-1165-university-of-north-carolina-charlotte in Mathematics (M) at University of North Carolina - Charlotte.


Reviews for Intro to Discrete Structures


Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/25/15
Place Value Problems Math 1 165 1 E0 Find the least common multiple and the greatest common divisor of each of the following pairs of integers a m 2001 and n 1001 Solution The two numbers have no prime factors in common7 so their GOD is 1 and their LCM is their product7 2003001 b m23325 andn3272 Solution LCM 23325 72 and the GOD 32 c m p3 q2 r and n p2 q r3 where p7 q7 and r are different primes Solution gcd pzqr and lcm p3q2r3 Notice that we can nd the number of positive integer divisors of an integer N in terms of its prime factorization For example7 the number 21375k is a divisor of 213m5 if and only ifz39 S lj S m and k S 71 Find the number of divisors of each of the integers a m 2001 Solution 2001 3 23 297 so it has 1 11 11 1 8 divisors b n 1001 Solution This one too factors into a product of three distinct primes7 and therefore has 8 divisors c m23325 Solution The number of divisors is D 3 12 11 1 24 d n 32 72 Solution The number of divisors is D 2 12 1 9 e m p3 q2 r where p7 q7 and r are different primes Solution The number of divisors is D 3 12 11 1 24 A high school with 1000 lockers and 1000 students tries the following exper iment All lockers are initially closed Then student number 1 opens all the lockers Then student number 2 closes the even numbered lockers Then stu dent number 3 changes the status of all the lockers numbered with multiples of 3 This continues with each student changing the status of all the lockers which are numbered by multiples of his or her number Which lockers are closed after all the 1000 students have done their jobs Solution Build a table for the rst 20 lockers7 and notice that the lockers that end up open are those numbered 1497 and 16 This looks like the Place Value Problems 9 03 Math 1 165 squares Think about what it takes to make a locker end up open It takes and odd number of changes7 which means an odd number of divisors We know how to count the number of divisors of a number N 1011 pflquot N has DN 61 162 1 en 7 1 divisors So the issue is how can this last number be odd lts odd if each factor 61 1 is odd7 which means all the 61 have to be even This is true precisely when N is a perfect square Using the Euclidean Algorithm7 evaluate g GCD41447596 and h LC M41447 7596 Then solve the equation 9 4144z 7596y7 for integers z and y Solution Notice that the gcd of the two numbers is 4 We can either proceed as usual or we can divide both numbers by 4 and then solve the resulting problem Lets try solving 1899s 1036y 1 using the EA Write down all the divisions and begin the unwinding operations 1 171 7 85 2 1717 85 173 7171 78517386171 7851738686374173 868637344173785173 86 863 7 429 173 86 863 7 429 1036 7 863 51586374291036 515 1899 71036 7 429 1036 515 1899 7 944 1036 Multiplying both sides by 4 gives 4 515 7596 7 944 41447 so z 7944 and y 515 Let 17 b7 0 d7 and e be digits satisfying 4 abcde4 4abcde Find all ve of the digits Solution Let x abcde Then 410x4 400000z7 from which it follows that 39x 399984 and m 10256 A 10 gtlt 10 square is decomposed into exactly 75 squares of various integer sizes How many 3 gtlt 3 squares are in this decomposition 2 Place Value Problems Math 1 165 00 p H H H 3 Solution The largest square cannot be as large as 5 gtlt 5 because in this case the total number of squares would be less than 75 Let 2y2 and w denote the number of squares of area 149 and 16 respectively Then 2 4y 92 1611 100 and z y 2 w 75 Subtracting the later from the former yields 3y 7 82 15w 25 Since there are no integer solutions to 3y 82 10 we may conclude that w 0 There is only one solution to 3y 82 25 narnely y 3 and z 2 A two digit integer N that is not a multiple of 10 is k times the sum of its digits The number formed by interchanging the the digits is m times the sum of the digits What is the relationship between m and k Solution Note that 10a 7 b ka b and 10b a mb 1 Adding the two equations together it follows that k m 11 The do challenge httpdigicccorn do Solution Let m denote your four digit number and let M denote the rearranged nurnber Thenw7w E abcd 7 uvw2 0 mod 9 because the sets abcd and uvw2 are identical Therefore any three digits ofthe difference M7W determines the fourth one unless the fourth digit is 0 or 9 in which case we do not know which it is The crystal cabobble challenge httpwwwsinotradinguscrystalballhtrn Solution Notice that all the multiples of 9 except 90 and 99 have the same syrnbol Why is 10a b 7 a b always a multiple of 9 How many two digit positive integers N have the property that the sum of N and the number obtained by reversing the order of the digits of N is a perfect square Solution Let N 102 y Then 102 y 10y x 112 y must be a perfect square Since 1 S x y S 18 it follows that z y 11 There are eight such numbers 29 38 47 56 65 74 83 and 92 A check is written for 2 dollars and y cents both 2 and y two digit numbers In error it is cashed for y dollars and 2 cents the incorrect arnount exceeding the correct amount by 1782 Find a possible value for z and y Solution Note that 100g 2 7 1002 y 99y 7 2 1782 It follows that y 7 z 18 so any pair of two digit numbers that differ by 18 will work Solve the alpha nurneric problern 2abc gtlt 4 cba2 where a b and c are decirnal digits Place Value Problems Math 1 165 H 9 H r H CH Solution We have 42000100a10bc 10000100b10a2 It follows quickly that c 8 Then 400a 4b 310 1001 10a Thus 39a 3 6b Only a 1 works and it follows that b 7 The rightmost digit of a six digit number N is moved to the left end The new number obtained is ve times N What is N Problems 14 though 16 also refer to 6 digit numbers Solution The number is 142857 Let N abcdef and let x abcde Then we have 5N 5abcdef fabcde Note that we have adopted the convention of underlining the digits of an integer in decimal notation For example Lb 10a b Note that 5abcdef 5abcd60 f 510x f fabcde 100000fm This leads to 50x72 100000f75f or 49x 99995f Factoring both sides gives 7 5 7 2857 f7 which is equivalent to 7x 5 2857 f7 from which it follows that f 7 Therefore z 14285 and N 142857 Repeat the same problem with the 5 changed to a 4 That is 4abcdef fabcde Solution There are several solutions7 N 1538467 N 102564N 205128 and N 230769 Next7 consider another transformation This time move the leftmost digit to the right end and change the 5 to a 3 Solution N 142857 or N 285714 Consider the problem you get when you move the right TWO digits to the left end Can this new number be exactly half the original number Find all solutions and prove that you have them all Solution Let N abcdef and let M Then 2efabcd abcdef translates into 210000106f x 100z106f Solving this for z yields 1999959205 0999243005 20439887106 f 204 gtlt105 f Since z is an integer7 the last equation requires that 106 f be a multiple of 14 Trying 14287 and 427 we see that they all work But 56707 and 84 all fail Thus the values of N are 28571475714287857142


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Jim McGreen Ohio University

"Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

Allison Fischer University of Alabama

"I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over $600 per month. I LOVE StudySoup!"

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

Parker Thompson 500 Startups

"It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.