Sock Drawer Problem Revisited

Problem 1 from Fifty Challenging Problems in Probability by Frederick Mosteller¶

"A drawer contains red socks and black socks. When two socks are drawn at random, the probability that both are red is $\frac{1}{2}$. How small can the number of socks in the drawer be?"

In July 2015 I took a first pass at this problem. Now I would like to consider other solutions to the sock drawer problem, beyond the smallest positive (fundamental) solution.

Starting with the probability of drawing 2 red socks, and treating the number of black socks as constant, we can set up a quadratic equation for $r$, and solve using the quadratic formula.

Let $r$ = number of red socks

Let $b$ = number of black socks

\begin{equation} Pr(2 Red) = \frac{r}{(r+b)}\frac{(r-1)}{(r+b-1)}=\frac{1}{2} \end{equation}

\begin{equation} 2r(r-1) = (r+b)(r+b-1) \end{equation}

\begin{equation} r^2-(2b+1)r+(b-b^2) = 0 \end{equation}

Quadratic Formula

\begin{equation} r = \frac{2b+1}{2} \pm \frac{\sqrt{(2b+1)^2-4(b-b^2)}}{2} \end{equation}

We know that $r > b$, so we can ignore the minus solution

\begin{equation} r = b + \frac{\sqrt{(2b+1)^2-4(b-b^2)}+1}{2} \end{equation}

\begin{equation} r = b + \frac{\sqrt{8b^2+1}+1}{2} \end{equation}

Since $r$ and $b$ are both integers, $\sqrt{8b^2+1}$ must be an odd number. Furthermore, $8b^2+1$ must be an odd perfect square.

Let $X^2 = 8b^2+1$

This is the Pell Equation: $X^2 - 8b^2 = 1$, which will have solutions closely connected to the continued fraction expansion of $\sqrt{8}$.

(See the preceeding blog post concerning the continued fraction expansion of a square root.)

\begin{equation} \sqrt{8} = 2 + \cfrac{1}{1 + \cfrac{1}{4 + \cfrac{1}{1 + \cfrac{1}{4 +\cdots } } } } \end{equation}

The "continued fraction machine" from MathForKids63 can be used to easily compute the first few convergents:

$$ \frac{2}{1},\frac{3}{1},\frac{14}{5},\frac{17}{6},\frac{82}{29},\frac{99}{35},...$$

Since the period is 2, then the second, fourth, and sixth convergents should provide solutions to $X^2 - 8b^2 = 1$

We can test the sixth convergent, $\frac{99}{35}$. Set $X=99$ and $b=35$

\begin{equation} (99^2) - 8(35^2) = 9801 - 8(1225) = 9801 - 9800 =1 \end{equation}

$b$ is the number of black socks. We can compute the number of red socks for this solution by substituting $X=99$ for the square root in the quadratic equation

\begin{equation} r = 35 + \frac{99+1}{2} = 85 \end{equation}

We can verify that 85 red socks and 35 black socks yields the desired probability of drawing two red socks. $Pr(2Red) = \frac{1}{2}$

By calculating more convergents, we can generate solutions to the Sock Drawer Problem for larger and larger numbers of socks.

Here is some simple Python to generate the first few solutions beyond the fundamental solution (which was R=3,B=1).

In [1]:

B = 1   # B represents number of Black Socks
B0 = 1
B1 = 1
R  = 1  # R represents number of Red Socks
X0 = 2       
X1 = 3
X  = 1  # X represents the Square Root of the Discriminant
        
for i in range(2,10):
    X = 4*X1+X0
    B = 4*B1+B0     
    X0 = X1
    X1 = X
    X = X1+X0
        
    B0 = B1
    B1 = B
    B = B1+B0
             
    X0 = X1
    X1 = X 
    B0 = B1
    B1 = B
            
    # compute B = Number of Black Socks
    R = int(B+(X+1)/2)

    print("Solution: ",i,"  Total Socks: ",R+B, "\tRed : ",R,"\tBlack : ",B )
        

Solution:  2   Total Socks:  21 	Red :  15 	Black :  6
Solution:  3   Total Socks:  120 	Red :  85 	Black :  35
Solution:  4   Total Socks:  697 	Red :  493 	Black :  204
Solution:  5   Total Socks:  4060 	Red :  2871 	Black :  1189
Solution:  6   Total Socks:  23661 	Red :  16731 	Black :  6930
Solution:  7   Total Socks:  137904 	Red :  97513 	Black :  40391
Solution:  8   Total Socks:  803761 	Red :  568345 	Black :  235416
Solution:  9   Total Socks:  4684660 	Red :  3312555 	Black :  1372105

The number of socks grows very quickly into the millions.