Can You Find A Matching Pair Of Socks?

Another week, another riddler. This one was from Kathy Bischoping:

I have 10 pairs of socks in a drawer. Each pair is distinct from another and consists of two matching socks. Alas, I’m negligent when it comes to folding my laundry, and so the socks are not folded into pairs. This morning, fumbling around in the dark, I pull the socks out of the drawer, randomly and one at a time, until I have a matching pair of socks among the ones I’ve removed from the drawer.

On average, how many socks will I pull out of the drawer in order to get my first matching pair?

(Note: This is different from asking how many socks I must pull out of the drawer to guarantee that I have a matching pair. The answer to that question, by the pigeonhole principle, is 11 socks. This question is instead asking about the average.)

Extra credit: Instead of 10 pairs of socks, what if I have some large number N pairs of socks?

This problem is just strict probabilities. The form of our answer is:

EV(p) = P(2,p) * 2 + P(3,p) * 3 + ... + P(p,p) * p

Where the probability of getting a sock at each pull is recursively discovered with

P(x,p) = (1 - \sum\limits_{k = 2}^x P(k-1,p)) (\frac {x-1}{2*p - x - 1})

As an example, here is what the probability looks like when you have three pairs of socks:

General form:

EV(3) = P(2,3) * 2 + P(3,3) * 3

P(2,3)

P(2,3) = (1 - \sum\limits_{k = 2}^x P(k-1,3)) (\frac {2-1}{2*3 - 2 - 1})

P(2,3) = 1 * (\frac {1}{3})

P(2,3) = \frac {1}{3}

P(2,3)

P(3,3) = (1 - \sum\limits_{k = 2}^x P(k-1,3)) (\frac {3-1}{2*3 - 3 - 1})

P(3,3) = (1 - \frac {1}{3}) * (\frac {2}{2})

P(3,3) = \frac {2}{3}

Putting it together:

EV(3) = \frac {1}{3} * 2 + \frac {2}{3} * 3

EV(3) = \frac {8}{3} \approx 2.667

Extending this to 10 gives us an answer of 5.675 socks removed from the drawer, on average.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s