Problem:
A drawer in a darkened room contains red socks, green socks, blue socks and black socks. A youngster selects socks one at a time from the drawer but is unable to see the color of the socks drawn. What is the smallest number of socks that must be selected to guarantee that the selection contains at least pairs? (A pair of socks is two socks of the same color. No sock may be counted in more than one pair.)
Answer Choices:
A.
B.
C.
D.
E.
Solution:
For any selection, at most one sock of each color will be left unpaired, and this happens if and only if an odd number of socks of that color is selected. Thus socks suffice: at most will be unpaired, leaving at least in pairs. However, will do! Since is not the sum of four odd numbers, at most socks out of will be unpaired. On the other hand, will not do: if the numbers of red, green, blue and black socks are , then four are unpaired, leaving pairs. Thus is the minimum.
Proceed inductively. If we require only one pair, then it suffices to select socks. Moreover, selecting socks doesn't guarantee a pair since we might select one sock of each color.
If we require two pairs, then it suffices to select socks: any set of socks must contain a pair; if we remove this pair, then the remaining socks will contain a second pair as shown above. On the other hand, socks might contain greens, black, red and blue -- hence only one pair. Thus socks is the smallest number to guarantee two pairs.
Similar reasoning shows that we must draw socks to guarantee pairs, and in general, socks to guarantee pairs. This formula is easily proved by mathematical induction. Thus socks are needed to guarantee pairs.