Take the 2-minute tour ×
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.

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|improve this question
1  
Since you have not posted many questions, I wanted to remind you of a few things about the site. In order to get the best possible answers, it is helpful if you say in what context you encountered the problem, and what your thoughts on it are so far; this will prevent people from telling you things you already know, and help them give their answers at the right level. If this is homework, please add the [homework] tag; people will still help, so don't worry. Also, many people find the use of the imperative ("Find", "solve") to be rude when asking for help. Please consider editing your question –  Arturo Magidin May 23 '12 at 18:04
    
@ArturoMagidin Thank you - added some context –  Felix May 23 '12 at 18:18
    
Thank you; this puts the problem in a much better light. –  Arturo Magidin May 23 '12 at 18:20

2 Answers 2

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|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|improve this answer

Your Answer

 
discard

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.