The Pigeonhole Principle • Introduction ○ If a flock of 20 pigeons roosts in a set of 19 pigeonholes ○ Then, one of the pigeonholes must have more than 1 pigeon. • Pigeonhole Principle ○ If k is a positive integer and k + 1 objects are placed into k boxes ○ Then at least one box contains two or more objects. • Proof ○ We use a proof by contraposition. ○ Suppose none of the k boxes has more than one object ○ Then the total number of objects would be at most k. ○ This contradicts the statement that we have k + 1 objects. • Corollary 1 ○ A function f from a set with k + 1 elements to a set with k elements is not one-to-one. • Proof ○ Use the pigeonhole principle. ○ Create a box for each element y in the codomain of f . ○ Put in the box for y all of the elements x from the domain such that f(x)=y. ○ Because there are k + 1 elements and only k boxes, at least one box has two or more elements. ○ Hence, f can’t be one-to-one. • Example ○ Among any group of 367 people, there must be at least two with the same birthday ○ Because there are only 366 possible birthdays. • Example ○ Show that for every integer n there is a multiple of n that has only 0s and 1s in its decimal expansion. ○ Let n be a positive integer. ○ Consider the n + 1 integers 1, 11, 111, … , 11…1 (where the last has n + 1 1s). ○ There are n possible remainders when an integer is divided by n. ○ By the pigeonhole principle, when each of the n + 1 integers is divided by n, at least two must have the same remainder. ○ Subtract the smaller from the larger and the result is a multiple of n that has only 0s and 1s in its decimal expansion. The Generalized Pigeonhole Principle • The Generalized Pigeonhole Principle ○ If N objects are placed into k boxes ○ Then there is at least one box containing at least ⌈N/k⌉ objects. • Proof ○ We use a proof by contraposition. ○ Suppose that none of the boxes contains more than ⌈N/k⌉−1 objects. ○ Then the total number of objects is at most ○ k(⌈N/k⌉−1) k((⌈N/k⌉+1)−1)=N ○ where the inequality ⌈N/k⌉ ⌈N/k⌉+1 has been used. ○ This is a contradiction because there are a total of n objects. • Example ○ Among 100 people there are at least ⌈100/12⌉ = 9 who were born in the same month. • Example ○ How many cards must be selected from a standard deck of 52 cards to guarantee that at least three cards of the same suit are chosen? ○ We assume four boxes; one for each suit. ○ Using the generalized pigeonhole principle, at least one box contains at least ⌈N/4⌉ cards. ○ At least three cards of one suit are selected if ⌈N/4⌉ ≥3. ○ The smallest integer N such that ⌈N/4⌉ ≥3 is N = 2 ∙ 4 + 1 = 9. • Example ○ How many must be selected to guarantee that at least three hearts are selected? ○ A deck contains 13 hearts and 39 cards which are not hearts. ○ If we select 41 cards, we may have 39 cards which are not hearts along with 2 hearts. ○ However, when we select 42 cards, we must have at least three hearts. ○ (Note that the generalized pigeonhole principle is not used here.)
