Answer to Puzzle #52: Different Coloured Socks in a Draw.

52. 100 black and white socks are in a drawer. How many socks must you pull out before you are guaranteed to have a pair? Generalize to socks of N different colors.

A nice simple puzzle for now, help build our confidence, we'll do something harder soon I promise:

picture of a striped sockBefore reading the answer can I interest you in a clue?

Assumptions

To be clear we are assuming socks are either black or white, and a pair constitutes either two black or two white socks.

Two colours

Honestly I've heard all sorts of answers to this puzzle, 49, 51, 99, 101, and I know what people are thinking, they're answering a different question. They're answering how many socks must I pull out in order to have a white pair, a pair of a specific colour anyway. That is not what the question, the question just asks for a pair.

So lets think logically. If we pull out 1 sock that cannot be a pair. If we pull out two socks they could be different colours, they might not be of course, but we are interested in guaranteeing a pair.

Which brings us to three socks, worst case thus far is we have one black and one white sock. When we draw the third sock it has to be either black or white, thus forming a pair with one we have already. There's your answer 3 socks.

N different colours

So the worst case scenario when we have N different colours is that when we are trying to form a pair we actually pull out, by chance, one of each different colours, N socks. In that case, and in order to be guaranteed of forming a pair, since we already have one of each N colours the next one we pull out will have to be of one of the colours we already have and form a pair.

For N colours we must pull N + 1 socks.

This is always true, regardless of the relative numbers of the different coloured socks. 10 red, 5 green, 1 blue, 100 yellow, it's still 4 colours. Pull out five socks.

Anything Further?

At this point I need to address the ambiguity in the question. It's not clear if you have 100 black and 100 white, or 50 of each. I actually think the questioner may have been asking in such a way as to give you the option of assuming that the socks were, for example, all black with white spots. We don't stand for that nonsense round here. I feel the need to answer the questions as I find them and not edit them to suit my needs. I was told of for that at school. So I've allowed the ambiguity to persists. I just wont entertain it.

For further work I thought we could work out the probabilities, but given that the model is not clear, whether there are 100, or 200 or even N hundred socks there are too many versions of the answer for me to write up. Doesn't stop you though.





© Nigel Coldwell 2004 -  – The questions on this site may be reproduced without further permission, I do not claim copyright over them. The answers are mine and may not be reproduced without my expressed prior consent. Please enquire using the link at the top of the page.
 


PayPal
I always think it's arrogant to add a donate button, but it has been requested. If I help you get a job though, you could buy me a pint! - nigel


This Website Uses Cookies

Mostly, but not entirely to remember if you have dismissed this very box. Also to increase the functionality of the site. The cookies I apply do not uniquely identify you, by continuing to use this site you agree to let me place a cookie. I also have advert and analytics providers, for more information click here here.x