The Pigeonhole Principle
The Pigeonhole Principle is the most praised mathematical tool I know. That is surprising because this principle sounds so trivial and self-evident: if you have more pigeons than pigeonholes and each pigeon must be in a pigeonhole, then at least one pigeonhole must contain more than one pigeon. That is all.
So, why is it so loved? It is because it can easily solve really complicated-looking problems. I will show a few short examples next.
Examples
1) Birthday Problem
If there are 367 people in a room, do two of them share the same birthday?
Yes, since there are only 366 possible birthdays (pigeonholes), including leap years, and 367 people (pigeons).
2) Pulling Socks
A drawer contains a mix of blue and white socks, each of which can be worn on either foot. If the socks are pulled without looking, what is the smallest number of socks that need to be pulled to guarantee a pair of the same color?
If we think of both colors as pigeonholes, we will need three pigeons to be sure that two of them get together.
3) First Letters
Prove that for every 27-word sentence in any English text, at least two words will begin with the same letter.
The English alphabet has 26 letters, so if we have 27 words, at least 2 words will begin with the same letter.
4) Same Amount of Hair
Prove that in New York City, there are two people who have the same number of hairs on their heads.
The human head can contain around 500,000 hairs. At the same time, there are millions of people in New York. So, at least two of them must share the same number of hairs on their heads.
5) Add Up To 9
Prove that if you choose five integers at random, from 1 to 8, then two of them must add up to 9.
There are four pairs of numbers between 1 and 8 that add up to 9: (1, 8), (2, 7), (3, 6), and (4, 5). If you choose five numbers at random, then by the Pigeonhole Principle, at least two of them must come from the same pair, and thus they must add up to 9.
6) Initials
Prove that if you have 700 people, there will be two of them who have the same initials for their first name and their first surname.
- We have 700 people.
- Each initial can have one of the 26 letters of the alphabet, which means that there are 26 × 26 = 676 possible combinations of first and last names.
- Since 700 (the number of people) is greater than 676 (the number of possible initials), by the Pigeonhole Principle, at least one combination of initials must be shared by at least two people.
7) Points inside a square:
Let us take four points located inside or on the edge of a square with side 1. Show that at least two of them are at a distance less than or equal to 1.
- The distance d between two points p and q is given by Pythagoras: d² = p² + q². Therefore, the biggest possible distance inside the square, which is the size of the diagonal, is √2 (d² = 1² + 1² = 2 ⇒ d = √2).
- In order to use the Pigeonhole Principle, let's divide the square into four smaller sub-squares of size ½.
- Every sub-square has a diagonal of √½, which is less than 1.
- Now we have four pigeonholes and four pigeons.
- By the pigeonhole principle, if we place four dots in these four smaller squares, at least one of the squares will contain at least one dot (distance ≤ √½).
- However, since we have exactly four dots and four squares, it is possible for every square to contain exactly one dot. In this case, the biggest distance between two points is 1.
- Therefore, in any configuration of the four points inside the square with side 1, at least two of them will be at a distance less than or equal to 1.
8) Numbered cards
A box contains 900 cards, numbered from 100 to 999. Cards are drawn at random (without replacement) from the box, and the sum of the digits on each drawn card is noted. What is the smallest number of cards that must be drawn to ensure that at least three of these sums are equal?
The answer is 53. Let's see why.
- The cards are numbered from 100 to 999, so each card has three digits.
- The smallest sum happens with 100: 1+0+0 = 1
- The biggest sum happens with 999: 9+9+9 = 27
- Therefore, all possible sums are between 1 and 27.
- Those two (1 and 27) are the only sums that do not repeat. The other 25 will appear in at least three cards.
- That means there are 2 pigeonholes for one pigeon each (1 and 27) and 25 pigeonholes for three pigeons or more.
- If we extract 2×1 + 2×25 = 52 cards, in the worst case we could have two cards for each sum without any repeating three times.
- So, by extracting one more card (53), for the Pigeonhole Principle, at least one of them will appear three times.
Sources: