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
\begin{equation*} \card{B} = n \lt m = \card{A} \text{.} \end{equation*}
Also let \(\funcdef{f}{A}{B}\) represent the function where \(f(a) = b\) means that object \(a\) has been placed in container \(b\text{.}\) 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 \(a_1,a_2\) with \(f(a_1) = f(a_2)\text{.}\)

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 \gt 200\text{,}\) there is no injection
\begin{equation*} \{\text{students who took a pudding}\} \ifuncto \{\text{bowls of chocolate pudding}\} \text{.} \end{equation*}
(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 \subseteq \{1,2,\dotsc, 20\}\text{.}\) How big must \(\card{A}\) be to ensure that there exist two elements of \(A\) whose sum is \(21\text{?}\)
Solution.
Collect together the (unordered) pairs of numbers that add to \(21\text{:}\)
\begin{equation*} B = \bigl\{ \{1,20\}, \{2,19\}, \dotsc, \{10,11\} \bigr\} \subseteq \powset{\{1,2,\dotsc, 20\}} \text{.} \end{equation*}
Notice that \(\card{B} = 10\text{.}\) Thinking of the elements of \(B\) as containers and elements of \(A\) as objects, place object \(a\) into container \(b\) if \(a \in b\text{.}\) We need one more object than container to ensure some container receives two objects, so the answer is \(\card{A} \ge 11\text{.}\)

Worked Example 20.5.6. Matching modulo \(m\).

Suppose \(m \in \N\) and \(A \subseteq \N\) such that \(0 \lt m \lt \card{A} \lt \infty\text{.}\) Show that there exist distinct \(a_1,a_2 \in A\) that have the same remainder when divided by \(m\text{.}\)
Solution.
The set of possible remainders is \(\natnumlt{m} = \{0,1,2,\cdots,m-1\}\text{.}\) Computing remainder after division by \(m\) defines a function \(A \to \natnumlt{m}\text{.}\) Since \(\card{\natnumlt{m}} = m \lt \card{A}\text{,}\) 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 \(\funcdef{f}{A}{B}\text{,}\) we can define an equivalence relation \(\mathord{\equiv}\) on \(A\) by taking \(a_1 \equiv a_2\) to mean \(f(a_1) = f(a_2)\) (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 \in A\) is “placed” in container \(b \in B\) when \(f(a) = b\text{.}\)
Consider the contrapositive:
if every equivalence class of \(A\) has no more than \(\ell\) elements, then \(\card{A} \le \ell \cdot \card{B}\text{.}\)
Since \(B\) is finite and \(f(A) \subseteq B\text{,}\) then also \(f(A)\) is finite and we can enumerate its elements. Write \(f(A) = \{ b_1, b_2, \dotsc, b_n \}\text{.}\) Each element of \(f(A)\) corresponds to an equivalence class of \(A\text{.}\)
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 \(a_i\) are representative elements of the class of elements of \(A\) that are mapped to \(b_i\) by \(f\text{.}\) In particular, we must have \(f(a_i) = b_i\) for each index \(i\text{.}\)
We are assuming that each class \([a_i]\) contains no more than \(\ell\) elements; i.e. \(\card{[a_i]} \le \ell\text{.}\) Since an equivalence relation always partitions a set \(A\) into the disjoint union of its equivalence classes, we have
\begin{align*} \card{A} \amp = \card{[a_1]} + \card{[a_2]} + \dotsb + \card{[a_n]} \\ \amp \le \underbrace{\ell + \ell + \dotsb + \ell}_{r \text{ terms}} \\ \amp = \ell n \\ \amp = \ell \cdot \card{f(A)}. \end{align*}
But \(f(A)\) is a subset of the finite set \(B\text{,}\) and so \(\card{f(A)} \le \card{B}\text{.}\) Combining this with the calculation above gives
\begin{equation*} \card{A} \le \ell \cdot \card{f(A)} \le \ell \cdot \card{B} \text{.} \end{equation*}

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 \(\ell = 2\text{:}\) we have \(13\) objects and \(6\) containers, and \(13 \gt 2 \cdot 6\text{.}\) (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 \(\card{A} \le \ell \cdot \card{B}\) and \(\card{A} \gt \ell \cdot \card{B}\) is when \(f\) is surjective and each of the equivalence classes has exactly \(\ell\) elements. When \(f\) is surjective, there are \(\card{B}\) equivalence classes in \(A\text{.}\) Since \(A\) is the disjoint union of its equivalence classes under \(\equiv\text{,}\) we have \(\card{A} = \ell \cdot \card{B}\text{.}\) If we add one more element to \(A\text{,}\) it will have to be included in one of the equivalence classes, and that class will now have size greater than \(\ell\text{.}\)

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\cdot 49 = 147\) students. After the \(\nth[148]\) 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 \(\ell\) to use, consider that “at least half” in this problem means “at least \(50\)”, which is the same as “more than \(49\)”. So choose \(\ell = 49\text{.}\) In that case, we need \(m \gt 49 \cdot 3 = 147\text{,}\) bringing us to the answer of \(m = 147 + 1 = 148\) students.
<Prev^TopNext>