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