Detailed mathematical approach

Problem Summary

Let \(b\) be the number of blue discs and \(n\) the total number of discs. Drawing two discs without replacement, the probability that both are blue is

$\frac{b}{n}\cdot\frac{b-1}{n-1}=\frac{1}{2}.$

So the integer pairs we seek satisfy

$2b(b-1)=n(n-1).$

The task is to find the first valid arrangement with \(n \gt 10^{12}\). The first such pair is \(b=756872327473\) and \(n=1070379110497\).

A direct search over all totals is far too slow, because valid pairs are extremely sparse. The key is that the quadratic condition above is equivalent to a negative Pell equation, which turns the search into a tiny recurrence loop.

Mathematical Approach

The entire solution comes from replacing a probability statement with an integer equation whose solutions can be generated exactly and in increasing order.

From probability to an integer equation

The probability of drawing two blue discs without replacement is

$\frac{\binom{b}{2}}{\binom{n}{2}}=\frac{b(b-1)}{n(n-1)}.$

Setting this equal to \(1/2\) gives

$\frac{b(b-1)}{n(n-1)}=\frac{1}{2}\qquad\Longleftrightarrow\qquad 2b(b-1)=n(n-1).$

This is already a Diophantine equation, but not yet in a form that exposes a clean recurrence.

Center the variables at odd integers

Multiply by \(4\) and complete the squares:

$8b^2-8b=4n^2-4n,$

$2(2b-1)^2-2=(2n-1)^2-1.$

Rearranging gives

$ (2n-1)^2-2(2b-1)^2=-1. $

Now define

$x=2n-1,\qquad y=2b-1.$

Then every valid arrangement corresponds exactly to an integer solution of

$x^2-2y^2=-1.$

This is the negative Pell equation for \(D=2\). Because \(x\) and \(y\) are odd, the inverse substitution \(n=(x+1)/2\), \(b=(y+1)/2\) always returns integers.

The Pell successor and the preserved invariant

Write a solution as \(x+y\sqrt{2}\). Multiplying by \(3+2\sqrt{2}\) produces

$x'+y'\sqrt{2}=(3+2\sqrt{2})(x+y\sqrt{2}),$

so

$x'=3x+4y,\qquad y'=2x+3y.$

The norm \(N(u+v\sqrt{2})=u^2-2v^2\) is multiplicative, and

$N(3+2\sqrt{2})=3^2-2\cdot 2^2=1.$

Therefore

$x'^2-2y'^2=N(x'+y'\sqrt{2})=N(3+2\sqrt{2})N(x+y\sqrt{2})=1\cdot(-1)=-1.$

So the Pell invariant is preserved exactly. Starting from the smallest positive solution \((x,y)=(1,1)\), repeated multiplication by \(3+2\sqrt{2}\) generates the positive solutions in increasing order.

Convert the Pell step back to disc counts

Substitute \(x=2n-1\) and \(y=2b-1\) into the Pell recurrence:

$2n'-1=3(2n-1)+4(2b-1),$

$2b'-1=2(2n-1)+3(2b-1).$

After simplifying, we obtain the recurrence used by the implementations:

$\boxed{b'=3b+2n-2,\qquad n'=4b+3n-3.}$

This affine update preserves the original invariant \(2b(b-1)=n(n-1)\), and every step increases both \(b\) and \(n\), so the first solution exceeding a threshold is found by plain iteration.

Worked example: from \((15,21)\) to \((85,120)\)

A known nontrivial solution is \((b,n)=(15,21)\). Apply one recurrence step:

$b'=3\cdot 15+2\cdot 21-2=85,$

$n'=4\cdot 15+3\cdot 21-3=120.$

Check the invariant:

$2\cdot 85\cdot 84=14280,\qquad 120\cdot 119=14280.$

So \((85,120)\) is another exact solution, and indeed

$\frac{85}{120}\cdot\frac{84}{119}=\frac{1}{2}.$

The sequence continues

$ (15,21)\to(85,120)\to(493,697)\to(2871,4060)\to\cdots $

and the first pair with \(n \gt 10^{12}\) is

$\boxed{(b,n)=(756872327473,\ 1070379110497).}$

Why the search is tiny

The linear part of the recurrence has dominant growth factor \(3+2\sqrt{2}\approx 5.828\). So the size of the solution is multiplied by roughly \(5.8\) at each step. That means only \(O(\log T)\) steps are needed to pass a threshold \(T\), which is why the \(10^{12}\) target is reached after only a small number of iterations.

How the Code Works

The C++, Python, and Java implementations all keep only the current pair \((b,n)\) and the threshold \(10^{12}\). Instead of beginning with the trivial tiny solutions, they seed the process at \((15,21)\), which is already a valid arrangement in the same Pell-generated sequence.

Each loop iteration applies the exact update

$b\leftarrow 3b+2n-2,\qquad n\leftarrow 4b+3n-3,$

then tests whether the new total has crossed the limit. As soon as \(n \gt 10^{12}\), the algorithm outputs the current blue count.

The C++ implementation also includes small checkpoint validations on known solutions and allows the threshold to be changed from the command line, but the mathematical core is identical in all three languages. For this problem the values remain comfortably within signed 64-bit range, so the arithmetic is straightforward in C++ and Java, while Python handles the same recurrence with native integers.

Complexity Analysis

Let \(T\) be the minimum total-disc threshold. Because the recurrence grows by a constant factor \(3+2\sqrt{2}\), the number of loop iterations is \(O(\log T)\). More precisely, it is about \(\log_{3+2\sqrt{2}} T\).

For the specific target \(T=10^{12}\), starting from \((15,21)\), the loop runs only 14 updates before reaching \(n=1070379110497\). Each update uses constant-time integer arithmetic on a fixed number of values, so the practical runtime is negligible. Memory usage is \(O(1)\).

Footnotes and References

1. Project Euler, Problem 100: https://projecteuler.net/problem=100
2. Pell's equation: Wikipedia - Pell's equation
3. Square root of 2: Wikipedia - Square root of 2
4. Recurrence relation: Wikipedia - Recurrence relation