Socks in a Drawer

I’ve began studying some probability and statistics for fun, and I’m using a book called Fifty Challenging Problems in Probability by Mosteller:

Printing math textbooks is a great way to use up the school’s printing credits at the end of the year.

The first problem is about socks in a drawer. At first glance it looks really, deceptively simple. But when I start doing the problem I find that it’s a bit trickier than I expected.

Solutions to the problems are provided at the back of the book. For this problem, I find that the book’s solution is really ugly and unintuitive. Thus I’m going to give an alternate solution here.

Problem (my version)

A drawer contains red and black socks. I randomly take a sock out of the drawer. I then randomly take another sock out of the drawer.

The probability that both are red is exactly \frac{1}{2}. Determine how many socks of each color there are in the drawer.

Solution

Let r be the number of red socks in the drawer, and b be the number of black socks. Then the total number of socks in the drawer is r+b.

The probability that a sock you randomly take is red would be

\frac{r}{r+b}

Now the probability that the next sock you take would also be red is

\frac{r-1}{r+b-1}

This is because there is one less red sock in the drawer, and at the same time there is one less sock (of any color) in the drawer.

The probability that both socks will be red is the two probabilities multiplied:

P = \frac{1}{2} = \frac{r}{r+b} \cdot \frac{r-1}{r+b-1}

Now we’re solving the equation to find possible values of r and b. There are two variables, and one equation. However, both variables have to be positive integers. This type of equation is called a diophantine equation.

We begin by simplifying the equation into a quadratic.

\begin{array}{rcl} \frac{r(r-1)}{(r+b)(r+b-1)} &=& \frac{1}{2} \\(r+b)(r+b-1)&=& 2r(r-1) \\ r^2+2rb+b^2-r-b&=&2r^2-2r \\ r^2+(-2b-1)r+(b-b^2)&=&0 \end{array}

Now using the quadratic formula to solve for r:

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

It’s not necessary to consider the negative root of the quadratic. Simplifying the quadratic further, we get

r = \frac{(2b+1)+ \sqrt{8b^2+1}}{2}

Here we can make a substitution. Let k = \sqrt{8b^2+1} . Then,

r = \frac{(2b+1)+ k}{2}

In this equation r will be an integer as long as b is an integer and k is an odd integer.

We are now finding integer solutions to the equation

k = \sqrt{8b^2+1}

..where k is also odd.

Simplifying, we get:

\begin{array}{rcl} k^2 &=& 8b^2+1 \\ k^2-8b^2&=&1 \end{array}

At this point we can drop the condition that k is odd, because if k is even then left hand side is even, but the right hand side is 1. As a result, k cannot be even if it’s a solution to this equation.

We’ve basically converted this problem into a form of Pell’s equation, which generally has this form:

x^2 - Dy^2 = 1

..where D is a constant and x and y are unknown integers. Our instance of Pell’s equation is the case where D=8.

Fortunately for us, the Pell’s equation is well studied. We can use existing results in number theory to help us with this problem.

By trial and error, it can be found that the smallest nontrivial solution, or the fundamental solution to the equation is (k,b) = (3,1). Once the fundamental solution to a Pell type equation has been found, all other solution pairs can be generated. And there are infinitely many such pairs.

Generating solution pairs can be done with this recurrence relation:

\begin{array}{rcl} k_{i+1} &=& k_1 k_i + D b_1 b_i \\ b_{i+1} &=& k_1 b_i + b_1 k_i \end{array}

It’s simple to write a computer program to generate these pairs. For instance, the first ten pairs of (k,b) are:

(3,1)
(17,6)
(99,35)
(577,204)
(3363,1189)
(19601,6930)
(114243,40391)
(665857,235416)
(3880899,1372105)
(22619537,7997214)

All that is left is to substitute values of b to get integer values of r. The first ten pairs of (r,b) are:

(3,1)
(15,6)
(85,35)
(493,204)
(2871,1189)
(16731,6930)
(97513,40391)
(568345,235416)
(3312555,1372105)
(19306983,7997214)

We are done; we can use the same recurrence relation to generate arbitrarily large sock combinations.

One thought on “Socks in a Drawer

  1. Thank you very much for your solution that I also find much better than the one displayed in the book. It helped me a lot and I learned about Pell’s equation, which is nice !

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s