The pigeonhole principle
Tonight's idea
If 10 pigeons fly into 9 pigeonholes, some hole gets at least two pigeons. The surprise is how much that proves.
Pigeonhole principle. If \(N\) objects are placed in \(k\) boxes and \(N > k\), some box holds at least 2. More precisely, some box holds at least \(\lceil N/k \rceil\) objects (\(N/k\) rounded up). Proof: if every box held fewer than \(N/k\), the total would be less than \(N\).
Hairs. A human head has at most about 150,000 hairs, and London has about 9 million people. Boxes: the 150,001 possible hair counts. Pigeons: the Londoners. So two Londoners have exactly the same number of hairs, and some count is shared by at least \(\lceil 9{,}000{,}000 / 150{,}001 \rceil = 60\) people. Pigeonhole proves existence without finding anything.
Every problem tonight is really the question: what are the pigeons, and what are the holes?
Watch one: a multiple of 7 made of 1s and 0s
Claim: some multiple of 7 is written using only the digits 1 and 0. Look at the eight numbers \(1, 11, 111, \ldots, 11111111\) and their remainders on division by 7. There are only 7 possible remainders and 8 numbers, so two of them, with \(a\) ones and \(b\) ones (\(a > b\)), leave the same remainder. Their difference is a multiple of 7, and it is \(a - b\) ones followed by \(b\) zeros (for instance \(11111 - 11 = 11100\): three 1s, then two 0s).
Pigeons: the 8 repunits (numbers written with only 1s). Holes: the 7 remainders. The proof never found the multiple (it is \(111111 = 7 \times 15873\)), and the same argument works for any divisor in place of 7.
Your turn
- In any group of 13 people, two share a birth month. How many people are needed to guarantee that three share a birth month? Explain with the \(\lceil N/k \rceil\) form.
- A drawer has 10 black, 10 blue and 10 grey socks. You pull socks out in the dark. How many must you take to be sure of a matching pair? How many to be sure of a black pair?
- Five points are placed anywhere inside a \(1 \times 1\) square. Prove that two of them are at most \(\sqrt{2}/2 \approx 0.707\) apart. (Hint: cut the square into four smaller squares.)
- Choose any 51 numbers from 1 to 100. Prove that one of them divides another. (Hint: write each number as \(2^j \times m\) with \(m\) odd. How many possible odd parts \(m\) are there?)
Stretch: a block that sums to a multiple of 10
Pick any 10 whole numbers \(a_1, \ldots, a_{10}\). Prove that some block of neighbours \(a_i + a_{i+1} + \cdots + a_j\) adds up to a multiple of 10. (Hint: the pigeons are the running totals \(a_1\), \(a_1 + a_2\), \(a_1 + a_2 + a_3\), and so on. What are the holes?)
Answers
- 25 people. With 12 months as boxes, \(\lceil 25/12 \rceil = 3\), so some month has at least 3. With 24 people, two per month is possible, so 24 is not enough.
- 4 socks: three colours are the boxes, so 4 socks force two of one colour. For a black pair, the worst case is all 10 blue and all 10 grey first, then two black: 22 socks.
- Cut the unit square into four \(\frac12 \times \frac12\) squares. Five points, four small squares: two points share a small square (a point on a boundary can be assigned to either). Two points in a \(\frac12 \times \frac12\) square are at most a diagonal apart: \(\sqrt{\frac14 + \frac14} = \frac{\sqrt{2}}{2}\).
- Every number from 1 to 100 is \(2^j \times m\) with \(m\) one of the 50 odd numbers 1, 3, ..., 99. Boxes: the 50 odd parts. 51 numbers: two share an odd part, say \(2^a m\) and \(2^b m\) with \(a \lt b\), and the first divides the second. With only 50 numbers the claim can fail: 51, 52, ..., 100 has no number dividing another.
Stretch. Let \(s_i = a_1 + \cdots + a_i\). If some \(s_i\) is a multiple of 10, done. Otherwise each of the ten sums has one of the 9 remainders 1 to 9, so two of them, \(s_i\) and \(s_j\) with \(i \lt j\), share a remainder, and \(s_j - s_i = a_{i+1} + \cdots + a_j\) is a multiple of 10. The same argument works for any \(n\) numbers and divisor \(n\).