Honors Discrete Mathematics
Honors Discrete Mathematics MAD 2104
Popular in Course
Popular in Mathematics Discrete
This 6 page Class Notes was uploaded by Dino Corwin on Monday October 12, 2015. The Class Notes belongs to MAD 2104 at Florida Atlantic University taught by Jorge Viola-Prioli in Fall. Since its upload, it has received 7 views. For similar materials see /class/221637/mad-2104-florida-atlantic-university in Mathematics Discrete at Florida Atlantic University.
Reviews for Honors Discrete Mathematics
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/12/15
24THE PIGEONHOLE PRINCIPLE As an application of the Principle of Mathematical Induction we present the Pigeonhole Principle which has a very simple statement and provides striking applications of diverse nature Pigeonhole Principle If more than n balls are placed into n boxes then there is at least one box containing more than one ball Proof Let us proceed by induction It clearly holds true for n 1 Assume the principle holds true for k boxes and suppose we have k1 boxes and 5 balls with s gt k1 Look at the k1th box if it contains more than one ball we are done If it contains a no ball or b exactly one ball then we look at the boxes 1 to k In case a we have 5 balls into k boxes But 5 gt k1 so 5 gt k By inductive hypothesis one box contains more than one ball J Viola Prioli In case b we have now 5 1 balls into k boxes But 5 gt k1 so 5 1 gt k By inductive hypothesis one box contains more than one ball This completes the proof NOTE In the applications we will not be dealing with balls and boxes we only use them as a model In the examples below I will indicate what plays the role of balls and what of boxes Problem 12 prove that if ve dots are placed into the unit square then there are two dots no more than 1 unit apart Proof Join opposite vertices of the square with a segment so producing four equal triangles these are the quotboxes We have ve dots these are the quotballsquot By the Pigeonhole Principle there are two balls at least in one of the triangles One side of the triangle is 1 unit in length the others measure Q 2 and so the maximum length inside a triangle is 1 We are done NOTE In exercise 4 you must sharpen this result by resorting to a different partition ofthe square J Viola Prioli Problem 2 Explain why if two dice are tossed twelve times then two of their sums must coincide Reason the possible sums are 2 3 12 that is 11 values these are the boxes There are twelve tries these are the balls By the Pigeonhole Principle there are two tries at least that produce the same sum In many applications we are asked to guarantee a certain occurrence In that case it is helpful to resort to an argument called quotthe worst case scenario in which we identify the maximum number of tries for the nonoccurrence Thus we just add one more try to guarantee the occurrence The following problem is solved by this method Problem 3 Fifty balls numbered 1 through 50 are in a box How many M be drawn to guarantee a a 50sum pair Solution We pair the numbers 149 2 48 2426 leaving 25 and 50 without companions Therefore the worst case scenario occurs when we draw 26 balls and end up with no 50sum pair We conclude that 27 is the answer J Viola Prioli Alternatively we have 26 boxes listed above so with 27 tries we are done Note that 27 is the minimum number to draw to guarantee the occurrence of course if we draw the fty balls we will end up with a 50sum pair but the statement includes the word must or equivalently the minimum number to produce the desired effect b two 50sum pairs Solution reason as before and conclude that the answer is 28 Observe that is not 27 27 c one 75sum pair Solution now we have 2550 2649 3738 1 2 24 that is 37 boxes Therefore the answer is 38 d one 99sum pair Solution notice that 49 50 is the only such pair leaving 48 singletons 1 48 Conclude that we must draw all the 50 balls with 49 balls we may end up with the 48 singletons plus only one number from 49 50 that being thus the worst case scenario J Viola Prioli Problem 4 How many cards must be dealt from a standard deck of cards to guarantee a a pair Solution since there are 13 cards of each of the four suits the answer is clearly 14 b a pair of aces Solution the worst case scenario is when we deal 49 cards and three aces still remain in the deck Thus the answer is 50 c two cards ofthe same any suit Solution there are four different suits that being thus the worst case scenario The answer is 5 d ve cards of same suit Solution the worst case scenario amounts to having four cards of each suit which makes 16 cards The answer is 17 J Viola Prioli NOTE 1 Read proposition 241 NOTE 2 It is very important to read the link with the examples and solutions posted on line See my Syllabus Section 24 J Viola Prioli
Are you sure you want to buy this material for
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'