The pigeonhole principle
Tonight's idea
If you put 10 pigeons into 9 pigeonholes, some hole gets at least two pigeons. You do not need to look inside. You do not need to know how the pigeons were arranged. There are more pigeons than holes, so a share is forced.
That is the whole principle. It sounds too obvious to be useful, and yet it proves things that look impossible to prove. The trick is always the same: decide what your pigeons are, decide what your holes are, and count both.
Three quick ones. In any group of 13 people, two were born in the same month (13 people, 12 months). In any group of 367 people, two share a birthday (366 possible birthdays counting 29 February). In a city of a million people, at least two have exactly the same number of hairs on their head, because nobody has more than about 200,000 hairs.
The stronger version: if you put \(n\) pigeons into \(k\) holes, some hole has at least \(n/k\) pigeons, rounded up. Put 25 pigeons in 4 holes and some hole has at least 7, since \(4 \times 6 = 24\) would only account for 24 of them.
The art is in choosing the holes. Often the holes are not objects at all but categories: remainders, colours, regions of a shape. Once you see the holes, the rest is counting.
Watch one: socks in the dark
A drawer holds red, blue and green socks, jumbled up. The light is off. How many socks must you pull out to be certain you have a matching pair?
The holes are the colours: 3 of them. The pigeons are the socks you pull. With 3 socks you might get one of each colour. With 4 socks, 4 pigeons go into 3 holes, so two socks share a colour. Answer: 4.
Notice what the principle does not tell you: it does not say which colour matches. It only guarantees that a match exists. That is typical. Pigeonhole proofs tell you something must happen without ever finding it.
Your turn
- A class has 30 students. Explain why at least 3 of them were born in the same month. Could you guarantee 4?
- The sock drawer now has red, blue, green and yellow socks. How many must you pull to guarantee a matching pair? How many to guarantee two disjoint matching pairs, using four different socks? (The pairs may be the same colour or different.)
- Pick any 5 whole numbers. Show that two of them leave the same remainder when divided by 4. Then explain why that means their difference is a multiple of 4.
- Five dots are placed anywhere inside a 2 by 2 square. Show that some two of them are no more than \(\sqrt{2}\) apart. (Hint: cut the square into four 1 by 1 squares. Assign a dot on a cut line to one of the small squares it touches. How far apart can two points in the same small square be?)
- At a party with at least two people, everyone shakes hands with some of the others (possibly none, never the same person twice). Show that two people shook exactly the same number of hands. (Hint: with \(n\) people, the possible counts are 0 up to \(n-1\). That is \(n\) holes for \(n\) people, which is not enough. Why can the counts 0 and \(n-1\) never both appear?)
Stretch: one divides another
Choose any 101 different numbers from 1 to 200. Prove that one of your numbers divides another one exactly.
Strong hint. Every whole number can be written as (an odd number) × (a power of 2). For instance \(12 = 3 \times 4\), \(40 = 5 \times 8\), \(7 = 7 \times 1\). Call the odd part the number's "odd core". How many different odd cores are possible for numbers from 1 to 200? Those are your holes. If two of your numbers share an odd core, what can you say about them?
Answers
- 30 students, 12 months. If each month had at most 2, that covers at most 24 students, leaving 6 unplaced. So some month has at least 3. You cannot guarantee 4: six months with 3 and six with 2 uses all 30 with no month reaching 4.
- 4 colours, so 5 socks force a pair. For two disjoint pairs: 7 socks. After 7 pulls, remove one matching pair; 5 socks remain, which force another pair using different socks. With 6 socks you could have 3 of one colour and 1 each of the others, leaving only one disjoint pair.
- Dividing by 4 leaves remainder 0, 1, 2 or 3: four holes. Five numbers into four holes, so two share a remainder. If \(a = 4p + r\) and \(b = 4q + r\), then \(a - b = 4(p - q)\), a multiple of 4.
- Cut the 2 by 2 square into four 1 by 1 squares, assigning every dot on a cut line to just one square it touches. Five dots, four small squares, so two dots are assigned to the same small square. The farthest apart two points of a 1 by 1 square can be is corner to opposite corner, which is \(\sqrt{1^2 + 1^2} = \sqrt{2}\).
- With \(n\) people the handshake counts run from 0 to \(n - 1\), which is \(n\) possibilities for \(n\) people, apparently just enough to all be different. But 0 and \(n - 1\) cannot both happen: someone who shook \(n - 1\) hands shook everyone's, including the person who supposedly shook nobody's. So only \(n - 1\) counts are really available for \(n\) people, and two people must share.
Stretch. The odd cores of numbers from 1 to 200 are the odd numbers from 1 to 199: there are 100 of them. You picked 101 numbers, so two of them, say \(a\) and \(b\), share an odd core \(m\): \(a = m \times 2^i\) and \(b = m \times 2^j\). Because the numbers are different, the exponents differ; rename them so \(i < j\). Then \(b = a \times 2^{j-i}\), so \(a\) divides \(b\). (With only 100 numbers it can fail: 101, 102, …, 200 has no number dividing another.)