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 . 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

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

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:

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.

Now using the quadratic formula to solve for r:

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

Here we can make a substitution. Let . Then,

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

..where k is also odd.

Simplifying, we get:

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:

..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 . 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:

It’s simple to write a computer program to generate these pairs. For instance, the first ten pairs of 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 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.