Problem
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?
Solution
from random import sample
num_sock_pairs = 30
runs = 10000
socks = list(range(num_sock_pairs))*2
total_num_socks = 0
for _ in range(runs):
samp = sample(socks, num_sock_pairs+1)
start_pos, end_pos = {}, {}
for i, sock in enumerate(samp):
if sock not in start_pos.keys():
start_pos[sock] = i
else:
end_pos[sock] = i
if sock in end_pos.keys():
break
total_num_socks += end_pos[sock]+1
print("Average number of socks ", total_num_socks/runs)