25 items, 8 boxes
⌈25/8⌉
4.
If items are put into boxes, some box contains at least items. In particular, if , some box holds two or more.
This page is easier if you are comfortable with:
Among 13 people at least two share a birth month (). If 100 items are placed in 7 boxes, some box has at least of them. Choosing 51 numbers from 1 to 100, two must be consecutive: pair the numbers as , 50 boxes, and . A drawer of black and white socks needs only 3 socks to guarantee a matching pair (, ). The ceiling function is the rounding up of division with remainder.
The proof is by contradiction: if every box held fewer than items, the total would be less than . The principle is non-constructive: it proves that a box exists without saying which one. It is the key step in the Ramsey argument (Ramsey numbers: a vertex in has 5 edges in 2 colours, so 3 share a colour) and bounds in coding theory (the Singleton bound).
Pigeonhole arguments prove existence results in number theory (two of any integers have the same remainder modulo , see congruences) and graph theory (two vertices of equal degree, using the handshaking lemma). The average argument behind it is the same as the first moment method.
If there are more items than boxes, some box must hold more than one item.
The fullest box holds at least the average, rounded up.
These examples are worked by hand, step by step, so you can compare your own working.
How many of 13 people must share a birth month, at least?
What is the least number in the fullest of 7 boxes holding 100 items?
Show that 51 numbers chosen from 1–100 include two consecutive ones. How many pairs (boxes)?
A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.
⌈25/8⌉
4.
⌈13/12⌉
2.
⌈100/7⌉
15.
3 socks guarantee a pair
Boxes + 1.
Putting n items in m boxes forces some box to hold at least ⌈n/m⌉ items; if n > m, some box holds two or more.
25 items in 8 boxes. Minimum in the fullest box.
13 people. Guaranteed to share a birth month?
100 events on 7 weekdays.
Two colours: how many socks guarantee a pair?
⌊25/8⌋ = 3 ✗
⌈25/8⌉ = 4 ✓
At least.
forgetting categories ✗
count the boxes ✓
Define them.
predicts the box ✗
only existence ✓
Not constructive.
Try each one on paper, then open the answer. Use the solver above to see the full working.
8
2
12
6
2
8
Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.
Solve: …
n items in m boxes put ⌈n/m⌉ in some box.
The fullest box has at least the average.
3.
No.
Ramsey numbers.
Catalan numbers.
More in Discrete maths and number theory and the formula sheets.