Question 1099269
.
Jim has many socks, all the same except that they are in eight different colours. He is leaving to catch an early train to go on a business trip, 
and does not want to wake his wife, so he must pack in the dark. He needs five pairs of socks, each sock in each pair the same colour. 
How many socks must he take from his drawer to be sure of achieving this?
~~~~~~~~~~~~~~~~~~~~~~~~


<pre>
So, Jim has many (VERY BIG NUMBER (!)) of socks in the drawer of eight colors:

    A B C D E F G H 

Hi starts pulling them in the dark one after other . . . 


In the worst scenario, he pulls out 8 socks of different color.
He even don't know (in the dark) what colors he just pulled out.
But he is smart enough and he knows that the sock #9 will make a pair with somewhat he pulled out before at his steps from 1 to 8.


Good. So, after 9-th step he definitely has a pair, although he doesn't know which exactly pair he has.

Let assume (together with Jim) that he just got the pair AA  (it does not matter at this moment what exactly pair).

At the pulling #10 he can pull out the sock of one of the remaining color 

                   B C D E F G H,  and then he is happy again: he has the second pair (let say BB). //But then he has 6 unpaired socks  C D E F G H.
                   But he also can pull out the sock of the color A, which only "starts" new pair, but not "completes" it yet.

                   So, the worst scenario at this step (step #10) is to pull out the sock A.

                   Therefore, in this case (been very smart) he must make next pulling up, which is #11.
                   And only after this pulling up #11 Jim can be sure that he has the pair #2.


Thus after step #9 Jim definitely has one par.
     After step #10 he EITHER  a)  has the second pair and 6 unpaired socks in his hands,
                       OR      b)  he needs to make the step #11 to get the second pair, having 7 unpaired socks at his hands.


In case a) he needs THREE steps ##11, 12 and 13 to guarantee the third pair.
In case b) he needs TWO   steps ##12 and 13 to guarantee the third pair.


Thus IN ANY CASE Jim needs 13 trials to guarantee 3 pairs.


You can continue this logic further from this step, but it is definitely clear that 13 pulling out are not enough.
</pre>