Counting · Definition
Pigeonhole principle
Before you start you need to know
It guarantees that something repeats without having to build it or know exactly how the objects are distributed.
Definition
If \(n\) objects are placed in \(k\) boxes, some box holds at least \(\lceil n/k\rceil\) objects, and in particular two when \(n>k\).
The basic statement is almost obvious: if there are more pigeons than nests, some nest receives two pigeons. Its strength lies in choosing the «boxes» well. In the problem of 13 people and 12 months the boxes are the months; with 8 integers and the 7 possible remainders on division by 7, the boxes are the remainders.
The general version says that if \(n>mk\), some box contains at least \(m+1\) objects; compactly, some box receives \(\lceil n/k\rceil\) or more. For example, 100 people in 12 months force some month to have \(\lceil 100/12\rceil=9\) people. To guarantee a given number one reasons backwards: the most one can avoid is \(m\) objects per box, that is \(mk\) in total, so object number \(mk+1\) breaks the avoidance.
The principle is existential only: it ensures there is a box with many objects, but it does not say which one or how to find it. Many proofs consist of inventing the boxes, such as the pairs \(\{a,\,13-a\}\) for sums equal to 13, or the residue classes modulo \(k\).
Typical mistakes: forgetting to round up (\(\lceil 7.5\rceil=8\), not 7), miscounting the boxes (there are 7 residues modulo 7, not 6), or using it to claim a box has exactly a given number of objects, when the principle gives only a lower bound.
Think about it
How many socks of 3 colours must be drawn blindly to be sure of a pair of the same colour?
Four: with three they can all differ in colour and the fourth repeats a colour (3 boxes, 4 objects).
If there are 25 objects in 6 boxes, can we be sure some box has exactly 5?
No. We are only sure of \(\lceil 25/6\rceil=5\) or more: some box has at least 5, but it could have more.
Exercises 10
- A group has 13 people. What can be stated with certainty about their birth months?
- 30 marbles are distributed into 4 boxes. What is the largest number that is guaranteed to be in some box at least?
- How many cards from a 52-card deck (4 suits) must be drawn at minimum to guarantee two of the same suit?
- How many people are needed at minimum to guarantee that at least 9 share a birth month, with 12 months?
- 100 people are grouped by birth month (12 months). At least how many are certain to share some month?
- How many integers must be chosen at minimum to guarantee two with the same remainder when divided by 7?
- A drawer holds loose socks of 3 colours. Without looking, how many must be taken at minimum to guarantee a pair of the same colour?
- A list has 1000 distinct Spanish words. Using 26 initial letters, how many words with the same initial can be guaranteed?
- Seven numbers are chosen from the set \(\{1,2,\dots,12\}\). Which statement is always true?
- 21 integers are chosen. At least how many are certain to end in the same units digit?
References
- Kenneth H. Rosen, Discrete Mathematics and Its Applications, 8th edition, McGraw-Hill, 2019. §6.2
- Susanna S. Epp, Discrete Mathematics with Applications, 5th edition, Cengage, 2019. §9.4
- Ralph P. Grimaldi, Discrete and Combinatorial Mathematics: An Applied Introduction, 5th edition, Pearson, 2003. §5.5