How it works
If you put more than n objects into n boxes, some box must hold at least two. That simple idea answers every "guarantee" question.
Use the worst case: make the picks as spread out as possible without reaching the goal, then one more pick forces it. To guarantee k of the same kind among t kinds, the worst case is k − 1 of every kind, so you need
t(k − 1) + 1
The boxes are whatever you sort by: colours, months, remainders or the last digit of a number.
Pigeonhole Principle practice problems with solutions
These problems come from Mathyessy's question bank. Try each one before opening the solution.
Marbles are red, blue, yellow, or green. How many must you draw to guarantee 2 of the same color?
Show answer and solution
Answer: 5
Worst case: one of each of the 4 colours. The 5th marble must match one of them.
Socks are red, blue, green, or black. How many socks must you grab to guarantee 5 of the same color?
Show answer and solution
Answer: 17
Worst case: 4 of each colour, which is 16 socks with no colour reaching 5. The 17th sock forces 5 of one colour: 4 × 4 + 1 = 17.
How many students are needed to guarantee 3 share the same birth month?
Show answer and solution
Answer: 25
Worst case: 2 students in each of the 12 months, which is 24. The 25th student makes 3 in some month.
6 types of candy. Minimum takes to guarantee 4 of one type?
Show answer and solution
Answer: 19
Worst case: 3 of each of the 6 types, 18 pieces. One more guarantees 4 of one type: 3 × 6 + 1 = 19.
Keep going
Related topics
All Counting & Probability topics · Contest math practice by topic · MATHCOUNTS practice · AMC 8 practice