Pigeonhole Principle

Suppose $P, k$ and $n$ are integers such that $P > k \times n$. If $P$ pigeons are placed into $n$ pigeonholes, then the pigeonhole principle states there must be (at least) one pigeonhole which contains at least $k+1$ pigeons.

Proof: The proof is by contradiction. Suppose there are no pigeonholes that contain at least $k+1$ pigeons, so each pigeonhole must contain at most $k$ pigeons. Since there are $n$ pigeonholes, there are at most $k \times n$ pigeons in total. This contradicts the fact that there are $P > k \times n$ pigeons in total. $_\square$

The power of the pigeonhole principle comes from choosing the correct pigeons and pigeonholes for the problem.

Worked Examples

1. In a standard deck of 52 cards, what is the minimum number of cards you need to pick up, in order to guarantee that there is a suit with at least 3 cards?

Solution: A standard deck has four suits, which forms our pigeonhole (so $n=4$). The cards are our pigeons. We want at least 3 cards in a suit, so $k+1 = 3$, implying $k=2$. Hence, if we have $9 = 2 \times 4 +1$, then by the pigeonhole principle, since there are $4$ suits (pigeonhole), there must be a suit which contains $3 = 2+1$ cards.

We are not yet done, as we want to know the minimum number. How do we know that $8$ cards are not sufficient to meet the requirements? Let's provide an example. The cards 2, 3 of clubs, 2, 3 of diamonds, 2, 3 of hearts, 2, 3 of spades are a set of $8$ cards which do not have a suit with at least 3 cards. Thus, the minimum number is 9.

2. There are 10 points placed within an equilateral triangle of side length 1. Show that we can find 2 points with distance at most $\frac {1}{3}$ apart.

Solution: If we have 2 points in an equilateral triangle of side length $A$, then these 2 points have distance at most $A$ apart. (Why? Convince yourself that if we have 2 points in ANY triangle, then the distance between these 2 points is at most the length of the longest side.) We are unable to apply the pigeonhole principle directly.

Cut up the equilateral triangle as follows:

Equilateral Triangle

Let our pigeons be the 10 points, and the pigeonholes be the 9 smaller equilateral triangles. By the pigeonhole principle, there must be 1 smaller equilateral triangle with at least 2 points in it. Then, these 2 points are at distance at most $\frac {1}{3}$ apart by our initial observation.

3. There are 6 people in a random Facebook group. Show that there are either 3 people who are all friends, or 3 people who are all strangers. Note: Remember that on Facebook, person A is friends with person B, then person B is friends with person A. Also, you are either a friend with, or a stranger to, another person.

Solution: We are unable to apply the Pigeonhole Principle directly. Consider any person A. Consider the other 5 people, who will be our pigeons. He is either friends or strangers (pigeonholes) with them. By the pigeonhole principle, there are (at least) 3 that he is either friends with, or strangers with. Let us assume that there are (at least) 3 whom he is friends with (otherwise interchange friends with strangers in the following discussion). Consider the group that are friends with A. If two of them are friends with each other, then the two of them along with A form a set of 3 people who are all friends. Otherwise, if none of them are friends with each other, then any three of them form a set of 3 people who are all strangers.