Can You Find a Matching Pair of Socks (Again)?

This Week's Fiddler

For the first sock drawn, there is no chance to make a pair. For the second, there is 1 possible pair to be made with 9 socks left, so there is a $\frac{1}{9}$ chance of making a pair. If the second draw doesn't yield a pair, then there are 2 possible pairs with 8 socks left, making a $\frac{2}{8}$ chance. However, for the chance that it's the first pair, it would be $(1-\frac{1}{9})\frac{2}{8}=\frac{2}{9}$.

Next up, 3 possible pairs with 7 socks left makes a $\frac{3}{7}$ chance, for a $(1-\frac{1}{9}-\frac{2}{9})\frac{3}{7}=\frac{2}{7}$ chance of being the first. Then 4 possible pairs with 6 socks left makes a $\frac{4}{6}$ chance, for a $(1-\frac{1}{9}-\frac{2}{9}-\frac{2}{7})\frac{4}{6}=\frac{16}{63}$.

With 5 possible pairs and 5 socks left, the sixth sock drawn guarantees a pair will be formed, meaning the remaining $1-\frac{1}{9}-\frac{2}{9}-\frac{2}{7}-\frac{16}{63}=\frac{8}{63}$ is the chance of needing six socks to draw one pair for the first time.

The highest chance of these is at the fourth sock, when there are 3 possible pairs to be made.

Answer: 4

Extra Credit

Creating a Python program to see how many pairs have already been drawn by the time the most likely time a pair is about to form:

for pow in range(8):
    n = 100**pow
    accum = 0
    best, best_k = 0, 0
    for k in range(1, n + 1):
        p = (1 - accum) * k / (2 * n - k)
        accum += p
        if p > best:
            best = p
            best_k = k
        else:
            break
    print(n, best_k)

1 1
100 14
10000 141
1000000 1414
100000000 14142
10000000000 141421
1000000000000 1414214
100000000000000 14142136

Notice that these are just the digits of $\sqrt2$ (rounded to the nearest integer for the given precision)! This would mean that the trend this follows, for $N$ pairs of socks, would be $\textrm{round}(\sqrt{2N})$.

The question we're answering is just a bit different, as it's how many socks should be drawn to achieve a pair. This is just 1 sock more than the number described here: $\textrm{round}(\sqrt{2N})+1$.

Although I wasn't sure how to concretely prove this, it's pretty fascinating that this emerges as such a clean trend!

Answer: round(sqrt(2N)) + 1