An old chestnut goes like this:

The power's out in my house this morning, and I need to find a pair of matching socks and a pair of matching shoes. The only source of light is a window which does not shine on the dark drawer where I keep my shoes and socks.

I don't want to pull out the entire drawer and carry it into the light, but I need to find two socks that match and two shoes that match. I don't care if the socks match the shoes.

There are 10 pairs of socks and 10 pairs of shoes in the drawer. 5 pairs of each are white, the other 5 pairs of each are black. Socks are interchangeable -- I can wear any sock on either foot, and any two of the same color will match. Shoes are not quite so interchangeable -- a pair must be a left shoe and a right shoe -- but any such pair of the same color will work.

If I pull out socks at random, what is the minimum number I can pull out to guarantee that when I carry them over to the light, I will find a pair among them?

If I pull out shoes at random, what is the minimum number I need to ensure a pair? How does the answer change if I can feel the shoes to determine if they are left or right shoes before pulling them out?

Answer:

To ensure a pair of socks, you only need to pull out 3 socks. If the first two are the same color, they make a pair. Otherwise, you have one of each color, and the third one must match one of them.

To ensure a pair of shoes, if you don't check for left/right shoes first, you need to pull out 11 shoes. If you only take 10, you could get all left shoes, or 5 white lefts and 5 black rights, and not have a pair. Having 11 ensures you have at least one shoe of 3 of the 4 distinct types (white left, white right, black left, black right), and that means that for one of the colors, you have both types of shoes.

If you can tell left and right shoes apart by feel, then you only need to pull out 7 shoes: one for one foot and six for the other. If you pull out 5 or fewer left shoes and 5 or fewer right shoes, it is possible to get all lefts of one color and all rights of the other. By pulling out six shoes for one foot, you ensure you get both colors for that foot. Then you just need any one shoe for the other foot to make a match.

Log in or register to write something here or to contact authors.