Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Going through a book of probability problems and am working on the Sock Drawer Problem:

A drawer contains red socks and black socks. When two socks are drawn at random, the probability that both are red is 1/2. How small can the total number of socks be?

I got as far as setting up and constraining the event as a function of the number of red socks (r) and black socks (b):

$$\frac{r(r-1)}{(r+b)(r+b-1)}=\frac{1}{2}; \qquad r, b \text{ are nonnegative integers.}$$

I want to find the minimum $b$ analytically. In a practical situation I'd just loop through possible values of b or graph it, of course.

share|cite|improve this question
up vote 3 down vote accepted

The problem said that there are red socks and black socks (plural). So perhaps one black sock does not qualify. With that as a (very thin) excuse, we look at the general problem.

Let $n$ be the total number of socks, and let $r$ be the number of red socks. With the changed notation, your equation becomes $$\frac{r}{(r-1)}{n(n-1)}=\frac{1}{2},$$ which can be rewritten as $n(n-1)=2r(r-1)$. Multiply both sides by $4$, and complete the squares. We arrive at the equation $$(2n-1)^2-2(2r-1)^2=-1,$$ which is a special case of a (negative) Pell Equation. So we look for solutions of the equation
$$x^2-2y^2=-1$$ in odd integers $x$ and $y$. (Odd because we want to set $2n-1=x$ and $2r-1=y$.) It turns out that all integer solutions of $x^2-2y^2=-1$ are odd, so we don't need to worry about this detail.

There is an obvious solution $(x_1,y_1)=(1,1)$. It is part of the standard theory of Pell equations that if $(x_n,y_n)$ is a positive solution of the equation, then $(x_{n+1},y_{n+1})$ is also a solution, where $$x_{n+1}=3x_n+4y_n \quad\text{and}\quad y_{n+1}=2x_n+3y_n.\tag{$1$}$$ Moreover, all positive solutions can be obtained in this way. This comes from the fact that in general $x_k+y_k\sqrt{2}=(1+\sqrt{2})^{2k-1}$. Or else, if we are more number-theoretically minded, we can talk about fundamental units of $\mathbb{Z}[\sqrt{2}]$. From this, we can obtain general formulas for $x_k$ and $y_k$ analogous to the familiar "Binet" formula for the Fibonacci numbers.

So starting at $(x_1,y_1)=(1,1)$, we get the solution $(x_2,y_2)=(7,5)$. This gives $2n-1=7$, $2r-1=5$, so $3$ red socks and a total of $4$ socks, so $1$ lone black sock.

The next solution is $(x_3,y_3)=(41,29)$, that is, $15$ red socks and a total of $21$. Here we have more than one sock of each kind, so perhaps $21$ is the intended answer.

But let's go on. Next comes $(x_4,y_4)=(239,169)$, so $85$ red socks and a total of $120$. And for people with more drawer space, there are arbitrarily large solutions.

There is a little more information about this particular Pell equation in an answer to a recent question. The subject is quite beautiful, and connects with many branches of mathematics.

share|cite|improve this answer
This answer is beautiful, thank you – Felix May 26 '12 at 10:43

$$\frac{r(r-1)}{(r+b)(r+b-1)} = \frac12$$ Lets try whether $b=1$ gives an integer value for $r$. Setting $b=1$ we get $$\dfrac{r(r-1)}{r(r+1)} = \frac12 \implies2r-2=r+1 \implies r=3$$ Hence, $b=1$ does the job for us.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.