The Pigeonhole Principle
Use the observation that more objects than boxes forces a repeat to prove existence results no construction would give.
What a learner can do afterwards
- State the principle and its generalised form with a ceiling
- Choose the pigeons and the holes for a stated problem, which is the whole difficulty
- Prove a result such as two people in a group sharing a handshake count
1 · Read
If you have more objects than boxes, some box must hold two. Four socks into three colours force two socks to share a colour. Thirteen people force two to share a birth month, since twelve months are the boxes. Sorting into boxes proves the result with no construction at all.
The generalised form sharpens the promise with a ceiling. With m objects in n boxes, some box holds at least m over n rounded up. Ten pigeons in 3 holes force 4 in one hole, since 10 over 3 rounds up to 4. The ceiling is sharp: one fewer object can always dodge, since 2 per hole absorbs 8 pigeons across 4 holes.
Choosing the pigeons and the holes is the whole difficulty. With 5 people, handshake counts look like 0 to 4, but 0 and 4 exclude each other: if someone shook none, nobody shook all. That leaves 4 live holes for 5 people, so two share a count. Choosing 7 numbers from 1 to 12 works the same way: the six complementary pairs summing to 13 are the holes, so one pair gives both members.
Name your containers before you count anything. Ask what is plentiful and what is scarce, then assign pigeons to the many and holes to the few. Five socks can dodge across five colours with one each, so the sixth sock forces the match. In birthday arguments, people are the pigeons and months are the holes.
Name your containers first, then let overfill do the proving.
2 · Watch
Take it off screen
Where it sits
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.