# How does one find the minimum of an equation of integers?

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.

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

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.

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