TwiddleLab / Math / Counting and Patterns
Pigeonholes
What you will learn
- Pigeonhole principle: put more than n things into n boxes, and some box gets at least two.
- More generally, some box gets at least N ÷ k, rounded up: 25 pigeons in 12 holes force a 3.
- It tells you what must happen, not what probably happens. Plan for the worst case.
- Hash tables live with it: more names than buckets means collisions are certain.
How the lesson goes
In a school of 400, must two people share a birthday?
Not probably. Must. What's your bet?
7 pigeons, 6 holes. Give each pigeon its own hole.
Drag them in one by one.
Now 12 holes, one per month. How many pigeons force 3 into one month?
The pigeons spread out as evenly as they can. Slide to find the smallest number.
With at most 2 per month, 12 months hold 24. So 25 forces some month to hold 3: 25 ÷ 12 rounded up is 3.
This is the pigeonhole principle.
Pigeonhole principle: n + 1 things in n boxes, and some box holds at least 2.
In general, N things in k boxes: some box holds at least N ÷ k, rounded up.
It says what must happen, whatever the arrangement.
Game: socks against the machine.
The drawer is dark and the machine always hands you the worst socks. Set how many to draw, then Draw.
5 dots in a 2 by 2 square. Try to keep them all far apart.
Drag them anywhere, then split the square.
Must it happen, or only maybe?
Drag each card into its box.
A hash table drops each name into a bucket by a formula.
Tap names to add them. Watch for two names in one bucket.
A class has 32 students. At least how many must share a birth month?
With 2 per month, 12 months take only 24 students, so with 32 some month must have at least 3.
More things than boxes: some box gets two.
Back to the hook. Pour the whole school into the calendar.
Previous lesson: Proof by Dominoes · Next lesson: Clock Arithmetic: Remainders · Part of the course: Counting and Patterns
Lessons are interactive and need JavaScript. Turn it on to play them.
