Some time ago, I tackled a sock puzzle:

I’m happy with my original solutions, but wanted to explore another way of doing it. It’s going to end up in a generalised Pell’s equation, so we’re looking at another example of great depth coming from a relatively simple puzzle.

As a reminder, the equations we need to solve are:

  • $\frac{r(r-1)}{n(n-1)} = \frac{1}{2}$
  • $\frac{b(b-1)}{n(n-1)} = \frac{1}{12}$
  • $r+b = n$

Those can be easily rearranged into:

  • $2r(r-1) = n(n-1)$
  • $12b(b-1) = n(n-1)$
  • $r+b = n$

To make square-completing easier, I’m going to multiply the first two equations by 4:

  • $2(2r)(2r-2) = 2n(2n-2)$
  • $12(2b)(2b-2) = 2n(2n-2)$

… or …

  • $2\left[ (2r-1)^2 -1 \right] = (2n-1)^2 - 1$
  • $12\left[ (2b-1)^2 - 1 \right] = (2n-1)^2 - 1$

I’m going to play with the first one:

  • $(2n-1)^2 - 2(2r-1)^2 = -1$

And that’s a version of Pell’s equation – its solutions for $(2r-1)$ and $(2n-1)$ lie among the convergents of the continued fraction of $\sqrt{2}$, where (in this case) the numerator and denominator are both odd.

So, what are those? The doubly-odd convergents are $\frac{1}{1}$, $\frac{7}{5}$, $\frac{41}{29}$, $\frac{239}{169}$ and so on, pointing to possible $(r,n)$ pairs of $(1,1)$, $(4,3)$, $(21,15)$, $(120, 85)$… infinitely many such solutions.

Can we do something similar with the other? Well, no. It doesn’t work for me, for reasons I don’t fully understand. However, if I eliminate $n$, I get:

  • $2(2r-1)^2 - 2 = 12(2b-1)^2 - 12$
  • $(2r-1)^2 - 6(2b-1)^2 = - 5$

That’s a little trickier, but it does fall to the general method:

  • find a solution $(x_0, y_0)$to the equation ( $x_0=(2n-1)=1$ and $y_0=(2b-1)=1$ works)
  • find the convergents $\frac{u_n}{v_n}$ of $\sqrt{6}$, which solve the equation with “1” on the right
  • Then let $x_n$ and $y_n$ be such that $(x_n + y_n \sqrt{6}) = (x_0 + y_0\sqrt{6})(u_n + v_n\sqrt{6})$
  • Then $x_n$ and $y_n$ satisfy the original equation.

What’s the continued fraction of $\sqrt{6}$?

Well, $\sqrt{6}$ is two-and-a-bit, so let’s call it $2+x$

  • $(2+x)^2 = 6$
  • $-2 + 4x + x^2 = 0$
  • $x(4+x) = 2$
  • $x = \frac{2}{4+x}$

But no, no, we want 1 on the top!

  • $x = \frac{1}{2 + x/2}$
  • $x = \frac{1}{2 + \frac{1}{4+x}}$

… and we can replace that $x$ as many times as we want, getting a progressively closer approximation to $\sqrt{12}$ each time.

So, what are the convergents to $\sqrt{6}$?

They’re $\frac{2}{1}$, $\frac{5}{2}$, $\frac{22}{9}$, $\frac{49}{20}$, $\dots$.

Those lead to possible $(u,v)$ pairs of $(8,3)$, $(17,7)$, $(76,31)$, $(169,69)$, etc., and – as before – we only need to look at the doubly-odd pairs.

$(17,7)$ points to an $(r,b)$ pair of $(9,4)$, which doesn’t quite work; $(169,69)$ leads to $(85,35)$, which coincides perfectly with the $(n,r) = (120,85)$ possibility we found earlier!

So, $r=85$, $b=35$ will work.

I’m not saying this is how you should approach the puzzle. I’m saying that the Pell’s equation is really neat, continued fractions are really neat, and combining them together to solve an already nice puzzle is about as tidy as I’m likely to find anywhere today.