Suppose you have a drawer containing 20 red socks 20 blue so

Suppose you have a drawer containing 20 red socks, 20 blue socks, and 20 green socks, and you can\'t see what sock you are taking from the drawer until you have already taken it out.

Determine the maximum number of socks you would have to take from the drawer to obtain 18 socks of the same color (i.e. in the worst case scenario), and prove your answer is correct.

In other words, prove that if you took fewer socks then it\'s possible that you wouldn\'t have 18 socks of the same color, but not if you took the right amount.

Solution

if you have N types of socks, you need to remove N+1 socks to guarantee a pair.

For the one pair you have to choose max 4 socks . You should have max 4 socks for one pair in your hand.

For the first pair you have to choose max 4 socks.

But for next 17 pairs you to have to choose max 2 socks for one pairs

So total no. of socks = 4*1+ 17*2 = 36 socks