KA-0157The pigeonhole principle
5 points, difficulty 3 of 3Level 7–8about 135sA drawer holds 12 red socks, 10 blue socks and 8 green socks, all mixed up. You take socks out one at a time in the dark. What is the smallest number of socks you must take to be certain of having three of the same colour?
Hints
Take them one at a time. The first gives nothing away.
1A nudge
Ask what the unluckiest possible draw looks like.
2The strategy
The worst case is taking two of every colour without ever getting a third. How many socks is that?
3The full solution
Two of each colour is 2 x 3 = 6 socks with no colour reaching three. The seventh sock must complete a set, so the answer is 7.
Solution
The reliable way
Imagine the unluckiest draw possible. You could take 2 red, 2 blue and 2 green - six socks - and still have no colour three times over. So six is not enough. But there are only three colours, so the seventh sock has to be red, blue or green, and whichever it is, that colour now has three. The answer is 7. The transferable idea: to guarantee something, work out the largest number of picks that could still fail, then add one.
The elegant way
Two of each colour is the largest failing draw at six socks, so seven forces success.
Why this is on the test: Guarantee questions are answered by the worst case, never by the likely case, and that reversal is the whole skill.