KA-0077The pigeonhole principle
5 points, difficulty 3 of 3Level 5–6about 120sA box holds 4 red, 5 blue and 6 green balls, mixed up. How many must be taken out without looking to be sure of having 3 of the same colour?
Hints
Take them one at a time. The first gives nothing away.
1A nudge
What is the unluckiest possible draw?
2The strategy
Ask how many balls you could take while still not holding three of any one colour. One more than that number forces a third of some colour, because there is nowhere new for it to go.
3The full solution
The worst case is two of each colour, which is 6 balls and still no set of three. The seventh ball must make a third of some colour.
Solution
The reliable way
Think about the worst case, not the lucky one. You could draw two red, two blue and two green — six balls with no colour appearing three times. But a seventh ball has to be red, blue or green, and whichever it is, that colour now has three. So 7 balls guarantee it and 6 do not. The transferable idea: fill every box to one short of the target, then add one.
The elegant way
With 3 colours acting as boxes, 7 balls cannot be spread with at most 2 per box, since 3 x 2 = 6.
Why this is on the test: To be sure means the worst case, and the answer is always one more than the largest arrangement that still fails.