Arranged Probability¶

We can rephrase this problem as finding integer solutions to $$\frac{b}{t} \times \frac{b-1}{t-1} = \frac{1}{2}$$ Specifically, we're looking for the first solution with $t > 10^{12}$. This is a Diophantine problem.

In [1]:
var('b,t')

sols = sorted(solve_diophantine(b/t * (b-1)/(t-1) == 1/2))
sols
Out[1]:
[(-1/8*(12*sqrt(2) + 17)^t*(7*sqrt(2) + 10) + 1/8*(-12*sqrt(2) + 17)^t*(7*sqrt(2) - 10) + 1/2,
  -1/8*sqrt(2)*((12*sqrt(2) + 17)^t*(7*sqrt(2) + 10) + (-12*sqrt(2) + 17)^t*(7*sqrt(2) - 10)) + 1/2),
 (-1/8*(12*sqrt(2) + 17)^t*(sqrt(2) + 2) + 1/8*(-12*sqrt(2) + 17)^t*(sqrt(2) - 2) + 1/2,
  -1/8*sqrt(2)*((12*sqrt(2) + 17)^t*(sqrt(2) + 2) + (-12*sqrt(2) + 17)^t*(sqrt(2) - 2)) + 1/2),
 (1/8*(12*sqrt(2) + 17)^t*(sqrt(2) + 2) - 1/8*(-12*sqrt(2) + 17)^t*(sqrt(2) - 2) + 1/2,
  1/8*sqrt(2)*((12*sqrt(2) + 17)^t*(sqrt(2) + 2) + (-12*sqrt(2) + 17)^t*(sqrt(2) - 2)) + 1/2),
 (1/8*(12*sqrt(2) + 17)^t*(7*sqrt(2) + 10) - 1/8*(-12*sqrt(2) + 17)^t*(7*sqrt(2) - 10) + 1/2,
  1/8*sqrt(2)*((12*sqrt(2) + 17)^t*(7*sqrt(2) + 10) + (-12*sqrt(2) + 17)^t*(7*sqrt(2) - 10)) + 1/2)]

Inspecting these parameterizations, the first two will always generate negative solutions for integer $t$, so we'll only consider the last two. We'll evaluate them at $t=0,1,2,\ldots$ to find the first instance where the total number of discs is greater than $10^{12}$.

In [2]:
from itertools import count

candidates = []
for sol in sols[2:4]:
    for n in count(0):
        b, t = sol[0](t=n), sol[1](t=n)
        if t > 10^12:
            candidates.append((b, t))
            break

Then we'll select the smaller $t$ of the two.

In [3]:
[(int(b), int(t)) for (b, t) in candidates]
Out[3]:
[(756872327473, 1070379110497), (4411375203411, 6238626641380)]

This tells us that $b=756872327473, t=1070379110497$ is the arrangement we're after.

Alternate method¶

However, we don't need SageMath's solve_diophantine for this problem. In fact, we can solve it using the same techniques as problem 45.

First, rearrange: $$2b^2 - 2b - t^2 + t = 0$$ Then complete the square: $$(2t-1)^2 - 2(2b-1)^2 = -1$$ Then substitute $X=2t-1$ and $Y=2b-1$ to get a Pell equation: $$X^2 - 2Y^2 = -1$$ The problem gives $b=85, t=120$ as a solution to the original equation; this corresponds to $X=239, Y=169$ for our Pell equation. To generate more solutions, we'll need a fundamental solution to this Pell equation, which we can find with SageMath, or with continued fractions, as in problem 66.

In [4]:
K.<sqrt2> = QQ[sqrt(2)]
u, *_ = K.units()
u
Out[4]:
sqrt2 + 1

With both of these values in hand, we can easily generate more solutions to $X^2 - 2Y^2 = -1$ by computing $\left(239+169\sqrt{2}\right)\left(1+\sqrt{2}\right)^k$ for successive values of $k$. Then we'll check to see if they correspond to solutions to our original equation.

In [5]:
z = 239 + 169*sqrt2
while True:
    z *= u
    if z.norm() != -1:
        continue
        
    x, y = z.parts()
    if (x + 1) % 2 != 0 or (y + 1) % 2 != 0:
        continue
        
    t, b = (x + 1) // 2, (y + 1) // 2
    if t > 10^12:
        break

As expected, we get the same solution as above.

In [6]:
b, t
Out[6]:
(756872327473, 1070379110497)

Copyright (C) 2025 filifa¶

This work is licensed under the Creative Commons Attribution-ShareAlike 4.0 International license and the BSD Zero Clause license.