Skip to main content
Logo image

Elementary Foundations: An introduction to topics in discrete mathematics

Jeremy Sylvestre

🔗

Section 20.5 Pigeonhole principle

🔗

Subsection 20.5.1 Regular strength version

Let A be the set of objects and B the set of containers, so that
|B|=n<m=|A|.
Also let f:A→B represent the function where f(a)=b means that object a has been placed in container b. Then the Theorem 20.5.1 tells us that f cannot be an injection, which means that there is at least one pair of distinct objects a1,a2 with f(a1)=f(a2).
🔗

Worked Example 20.5.3. Too few seats.

🔗
Your car has five seats, but you also have five friends who need a ride home. How will everyone fit?
Solution.
Using the people who need to get home (i.e. your friends and you) as objects and car seats as containers, Pigeonhole Principle says that someone will have to sit on someone else’s lap.
🔗

Worked Example 20.5.4. Dessert logistics.

🔗
The cafeteria puts out 200 chocolate puddings and 200 tapioca puddings. If 201 students each grab a bowl of pudding, what is the minimum number of tapioca puddings that have been taken?
Solution.
Since 201>200, there is no injection
{students who took a pudding}↪{bowls of chocolate pudding}.
(Or: use students as objects, bowls of chocolate pudding as containers.)
But we can’t actually have two students take the same bowl of pudding, so at least one student must eat tapioca.
🔗

Worked Example 20.5.5. Matching pairs.

🔗
Suppose A⊆{1,2,…,20}. How big must |A| be to ensure that there exist two elements of A whose sum is 21?
Solution.
Collect together the (unordered) pairs of numbers that add to 21:
B={{1,20},{2,19},…,{10,11}}⊆P({1,2,…,20}).
Notice that |B|=10. Thinking of the elements of B as containers and elements of A as objects, place object a into container b if a∈b. We need one more object than container to ensure some container receives two objects, so the answer is |A|≥11.
🔗

Worked Example 20.5.6. Matching modulo m.

🔗
Suppose m∈N and A⊆N such that 0<m<|A|<∞. Show that there exist distinct a1,a2∈A that have the same remainder when divided by m.
Solution.
The set of possible remainders is N<m={0,1,2,⋯,m−1}. Computing remainder after division by m defines a function A→N<m. Since |N<m|=m<|A|, this function cannot be an injection.
(Or: use elements of A as objects, possible remainders when dividing a number by m as containers.)
🔗

Subsection 20.5.2 Strong version

🔗
Recall that given a function f:A→B, we can define an equivalence relation ≡ on A by taking a1≡a2 to mean f(a1)=f(a2) (see Example 18.4.5). In this way, we can regard f as placing objects (elements of A) into containers (elements of B), so that object a∈A is “placed” in container b∈B when f(a)=b.
Consider the contrapositive:
if every equivalence class of A has no more than ℓ elements, then |A|≤ℓ⋅|B|.
Since B is finite and f(A)⊆B, then also f(A) is finite and we can enumerate its elements. Write f(A)={b1,b2,…,bn}. Each element of f(A) corresponds to an equivalence class of A.
Diagram of equivalence classes under the “have same image” equivalence.
Figure 20.5.8. Diagram of equivalence classes under the “have same image” equivalence.
In this diagram, the ai are representative elements of the class of elements of A that are mapped to bi by f. In particular, we must have f(ai)=bi for each index i.
We are assuming that each class [ai] contains no more than ℓ elements; i.e. |[ai]|≤ℓ. Since an equivalence relation always partitions a set A into the disjoint union of its equivalence classes, we have
|A|=|[a1]|+|[a2]|+⋯+|[an]|≤ℓ+ℓ+⋯+ℓ⏟r terms=ℓn=ℓ⋅|f(A)|.
But f(A) is a subset of the finite set B, and so |f(A)|≤|B|. Combining this with the calculation above gives
|A|≤ℓ⋅|f(A)|≤ℓ⋅|B|.
🔗

Worked Example 20.5.11. Handing out coins.

🔗
Show that if thirteen coins are distributed to six children, then at least one child will receive at least three coins.
Solution.
Using coins as objects and children as containers, the given statement is just the Pigeonhole Principle (strong form, formal version) with ℓ=2: we have 13 objects and 6 containers, and 13>2⋅6. (Note: Since coins are discrete objects, “more than two” and “at least three” are the same thing.)
🔗

Remark 20.5.12.

🔗
It is worthwhile to think about how the strong form of the Pigeonhole Principle could be proved directly. Consider the diagram in Figure 20.5.8: the “tipping point” between |A|≤ℓ⋅|B| and |A|>ℓ⋅|B| is when f is surjective and each of the equivalence classes has exactly ℓ elements. When f is surjective, there are |B| equivalence classes in A. Since A is the disjoint union of its equivalence classes under ≡, we have |A|=ℓ⋅|B|. If we add one more element to A, it will have to be included in one of the equivalence classes, and that class will now have size greater than ℓ.
🔗

Worked Example 20.5.13. Handing out pudding.

🔗
The cafeteria puts out 100 chocolate, 100 tapioca, and 100 butterscotch puddings. How many students must grab a pudding before we can be certain that at least one of the flavours has at least half of the bowls taken?
Solution 1. Using “tipping point” thinking
The “tipping point” is exactly 49 bowls of each flavour taken, which requires 3⋅49=147 students. After the 148th student, we will definitely have 50 bowls of one of the flavours taken.
Solution 2. Direct use of the Pigeonhole Principle
Consider students as objects (m of them — this is the unknown to be determined) and flavours as containers (3 of them). To determine the appropriate value of ℓ to use, consider that “at least half” in this problem means “at least 50”, which is the same as “more than 49”. So choose ℓ=49. In that case, we need m>49⋅3=147, bringing us to the answer of m=147+1=148 students.
<Prev^TopNext>