A draw contains an unsorted collection of black, navy, white, and brown coloured socks. If socks are taken at random, one at a time, what is the minimum number which must be taken to be certain of finding five matching pairs?
Obviously we could be lucky and take ten socks of which we have five matching pairs, but equally we might, for example, have taken eight black socks, one white sock, and one brown sock.
We shall approach this problem by a process called induction, which, simply put, means one thing leading to the next. We begin by considering the base case: how many socks are required to be certain that we have one matching pair?
The worst case scenario is that the first four socks could all be different colours, but the next sock must match one of the four. So we can be certain of picking at least one matching pair with five socks.
Suppose we took six socks. By our previous reasoning we can be certain that there is at least one matching pair, so let us remove this pair. However, now we cannot be certain that a matching pair will be found among the four remaining socks. Instead if we took seven socks we know that at least one pair matches, and by removing that pair we have five socks remaining of which we can be certain that a further matching pair could be found. In other words, we can be certain of finding two matching pairs among seven socks.
By continuing with this reasoning we can see that by increasing the number of socks by two each time we can be certain of selecting an additional matching pair. Therefore, the number of socks required to be certain of finding $p$ matching pairs is given by 2$p$ + 3.
Hence to be certain of selecting five matching pairs we must take 25 + 3 = 13 socks.
Can you obtain a formula to find the minimum number of socks which must be taken to be certain of finding $p$ matching pairs when the draw contains an unsorted collection of $c$ different coloured socks?