×

### Let's log you in.

or

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

×

or

by: Dino Corwin

7

0

6

# Honors Discrete Mathematics MAD 2104

Dino Corwin
FAU
GPA 3.8

Jorge Viola-Prioli

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

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

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

×
Unlock Preview

COURSE
PROF.
Jorge Viola-Prioli
TYPE
Class Notes
PAGES
6
WORDS
KARMA
25 ?

## 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

×

×

### What is Karma?

#### 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

×

×

### BOOM! Enjoy Your Free Notes!

×

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

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."

Jennifer McGill UCSF Med School

#### "Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over \$500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

Steve Martinelli UC Los Angeles

Forbes

#### "Their 'Elite Notetakers' are making over \$1,200/month in sales by creating high quality content that helps their classmates in a time of need."

Become an Elite Notetaker and start selling your notes online!
×

### Refund Policy

#### STUDYSOUP CANCELLATION 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 support@studysoup.com

#### STUDYSOUP REFUND POLICY

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: support@studysoup.com

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 support@studysoup.com