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

Fiddler

I have five distinct pairs of socks in my drawer, none of which is actually paired up. The room is pitch black, so I can’t see the color of any sock I’m pulling out. I reach into my drawer and randomly pull out one of the 10 socks. Then I reach in again and pull out one of the remaining nine. I can keep pulling out one sock at a time, at random, until I decide to stop at some point.

My goal is to stop removing socks as soon as I have a matching pair among those I have drawn. How many socks should I draw to maximize the chances that the last sock I draw results in the first such pair?

Solution

There are $10$ pullings. The first pair of socks can occur on pulls $2$ to $6$. After $6$, a pair is guaranteed to already exist because $5$ is the largest value with no pairs.

First Pair on Second Draw

1. The first pull can be any sock. $10$
2. The second pull has to match the previous sock. $1$
3. The remaining socks could be pulled in any order. $8!$

$$10 \cdot 1 \cdot 8! = \boxed{403,200}$$

First Pair on Third Draw

1. The first pull can be any sock. $10$
2. The second pull cannot match the previous sock. $8$
3. The third pull has to match one of the previous socks. $2$
4. The remaining socks could be pulled in any order. $7!$

$$10 \cdot 8 \cdot 2 \cdot 6! = \boxed{806,400}$$

First Pair on Fourth Draw

1. The first pull can be any sock. $10$
2. The second pull cannot match the previous sock. $8$
3. The third pull cannot match the previous socks. $6$
4. The fourth pull has to match one of the previous socks. $3$
5. The remaining socks could be pulled in any order. $6!$

$$10 \cdot 8 \cdot 6 \cdot 3 \cdot 6! = \boxed{1,036,800}$$

First Pair on Fifth Draw

1. The first pull can be any sock. $10$
2. The second pull cannot match the previous sock. $8$
3. The third pull cannot match the previous socks. $6$
4. The fourth pull cannot match the previous socks. $4$
5. The fifth pull has to match one of the previous socks. $4$
6. The remaining socks could be pulled in any order. $6!$

$$10 \cdot 8 \cdot 6 \cdot 4 codt 4 \cdot 5! = \boxed{921,600}$$

First Pair on Sixth Draw

1. The first pull can be any sock. $10$
2. The second pull cannot match the previous sock. $8$
3. The third pull cannot match the previous socks. $6$
4. The fourth pull cannot match the previous socks. $4$
5. The fifth pull cannot match the previous socks. $2$
6. The sixth pull has to match one of the previous socks. $5$
7. The remaining socks could be pulled in any order. $4!$

$$10 \cdot 8 \cdot 6 \cdot 4 \cdot 2 \cdot 5 \cdot 4! = \boxed{460,800}$$

Answer

You should draw $\boxed{\text{four}}$ socks to maximize the probabilty, which is

$$ \dfrac{1,036,800}{10!} = \boxed{\dfrac{2}{9}}$$

Extra Credit.

Instead of five pairs of socks, I now have N pairs of socks, where N is a very large number. In terms of N, how many socks should I draw to maximize the chances that the last sock I draw results in the first pair?

Solution

There are $2N$ pullings. The first pair of socks can occur on pulls $2$ to $N+1$. After $N+1$, a pair is guaranteed to already exist because $N$ is the largest value with no pairs.

First Pair on Second Draw

1. The first pull can be any sock. $2N$
2. The second pull has to match the previous sock. $1$
3. The remaining socks could be pulled in any order. $(2N-2)!$

$$2N \cdot 1 \cdot (2N-2)! = \boxed{\dfrac{(2N)!}{2N-1}}$$

First Pair on Third Draw

1. The first pull can be any sock. $2N$
2. The second pull cannot match the previous sock. $2(N-1)$
3. The third pull has to match one of the previous socks. $2$
4. The remaining socks could be pulled in any order. $(2N-3)!$

$$2N \cdot 2(N-1) \cdot 2 \cdot (2N-3)! = \boxed{\dfrac{2\cdot(2N)!}{2N-1}}$$

...

First Pair on $k^\text{th}$ Draw

1. The first pull can be any sock. $2N$
2. The second pull cannot match the previous sock. $2(N-1)$
3. ...
4. The $(k-1)^\text{st}$ cannot match the previous socks. $2(N-(k-2))$
5. The $k^\text{th}$ pull has to match one of the previous socks. $k-1$
6. The remaining socks could be pulled in any order. $(2N-k)!$

$$2^{k-1} \cdot _{N}P_{k-1} \cdot (k-1) \cdot (2N-k)! = \boxed{\dfrac{2^{k-1} \cdot (k-1) \cdot N! \cdot (2N-k)!}{(N-k+1)!}}$$

First Pair on $(k+1)^\text{st}$ Draw

1. The first pull can be any sock. $2N$
2. The second pull cannot match the previous sock. $2(N-1)$
3. ...
4. The $k^\text{th}$ cannot match the previous socks. $2(N-(k-1))$
5. The $(k+1)^\text{st}$ pull has to match one of the previous socks. $k$
6. The remaining socks could be pulled in any order. $(2N-(k+1))!$

$$2^k \cdot _{N}P_{k} \cdot k \cdot (2N-k-1)! = \boxed{\dfrac{2^k \cdot k \cdot N! \cdot (2N-k-1)!}{(N-k)!}}$$

The $k^\text{th}$ draw is the maximum if the $(k+1)^\text{st}$ draw has fewer possibilities than the $k^\text{th}$ draw, as this follows a Poisson distribution.

Dividing the $(k+1)^\text{st}$ draw count by the $k^\text{th}$ draw count,

\begin{align*} 2\cdot\dfrac{k}{k-1}\cdot\dfrac{N-k+1}{2N-k} &< 1 \\ \\ 2k(N-k+1) &< (k-1)(2N-k) \\ \\ -2k^2+2kN+2k &< -k^2+2kN+k-2N \\ \\ 0 &< k^2-k-2N \\ \end{align*}

Using the quadratic formula to solve the final step,

\begin{align*} k &= \dfrac{1 \pm \sqrt{1+8N}}{2} \\ \end{align*}

Answer

$$k = \boxed{\Bigg\lceil \dfrac{1 \pm \sqrt{1+8N}}{2} \Bigg\rceil}$$

Note that $0 < k^2-k-2N$ can expressed as $N < \frac{1}{2}k(k-1)$.

In other words, $k$ is the number of rows in the smallest triangular number greater than or equal to $N$.

Rohan Lewis

2024.07.01

Code can be found here.