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?
Found 2 solutions by greenestamps, ikleyn:
Answer by greenestamps(13203)   (Show Source):
You can put this solution on YOUR website!
The problem is to pick socks so that you know for sure that you have 5 pairs.
To answer a question like that, you need to use the "worst case" scenario. The worst thing that can happen is that the first 8 socks are all different colors. In that case the next 5 picks will create 5 pairs.
So the number of socks he needs to pull out of the drawer to guarantee having 5 pairs is 13.
Answer by ikleyn(52835)  (Show Source):
You can put this solution on YOUR website! .
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?
~~~~~~~~~~~~~~~~~~~~~~~~
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.
|
|
|
