Discrete Math › Section D · Counting › Topic D.9
The pigeonhole principle
Put more objects than boxes and some box must hold two. That almost obvious fact proves that collisions are unavoidable in hash tables, that no compression program can shrink every file, and many other results that feel surprising.
In this topic
- Guaranteed collisions
- The basic principle
- The generalised principle
- How many objects force a pile?
- Worked example: a pair that sums to 13
- Worked example: points in a square
- Remainders and friendships
- Pigeonholes in computing
- Common mistakes to avoid
- Key takeaways
This topic is part of Wuanberri Pro. Checking your access…