notes.html

problem 100 · 54 lines

<article>
<h3>Problem Analysis</h3>
<p>
The probability of drawing two blue discs in succession, without replacement, from a box of
<code>n</code> total discs containing <code>b</code> blue discs is
<code>(b/n) * ((b-1)/(n-1))</code>. Setting this equal to <code>1/2</code> and clearing
denominators gives <code>2 * b * (b - 1) = n * (n - 1)</code>. Because both quantities count
physical discs, only integer solutions matter, which makes this a
<a class="reference-source" href="https://en.wikipedia.org/wiki/Diophantine_equation" rel="noopener noreferrer" target="_blank">Diophantine equation</a> - a polynomial equation for which we seek integer solutions only. A naive search over all <code>n</code> up to <code>10^12</code> is hopeless, so the task is really to find hidden structure in this relation.
</p>
<p>
The decisive observation comes from
<a class="reference-source" href="https://en.wikipedia.org/wiki/Completing_the_square" rel="noopener noreferrer" target="_blank">completing the square</a> on both sides. Multiplying out and rearranging yields
<code>(2n - 1)^2 - 2 * (2b - 1)^2 = -1</code>. With the substitution <code>x = 2n - 1</code> and
<code>y = 2b - 1</code> this is exactly <code>x^2 - 2*y^2 = -1</code>, a classic
<a class="reference-source" href="https://en.wikipedia.org/wiki/Pell%27s_equation" rel="noopener noreferrer" target="_blank">Pell equation</a>. A
<a class="reference-source" href="https://en.wikipedia.org/wiki/Pell%27s_equation" rel="noopener noreferrer" target="_blank">Pell equation</a> of the form <code>x^2 - D*y^2 = ±1</code> has infinitely many integer solutions, all generated from a small fundamental solution by a fixed linear
<a class="reference-source" href="https://en.wikipedia.org/wiki/Recurrence_relation" rel="noopener noreferrer" target="_blank">recurrence relation</a>. Once this structure is recognised, the open-ended search collapses into a direct iteration: each step produces the next valid arrangement. Because the solutions grow geometrically (by a factor of roughly <code>3 + 2*sqrt(2) ≈ 5.83</code> per step), only about 40 iterations suffice to cross <code>10^12</code>. The overall complexity is <code>O(log T)</code> in the threshold <code>T</code>, with each iteration performing constant-time arithmetic.
</p>
<h3>Solution Approach</h3>
<h4>Iterating the Pell equation recurrence (Python and C)</h4>
<p>
Both files implement the same algorithm: iterate the linear recurrence that generates successive
solutions of the
<a class="reference-source" href="https://en.wikipedia.org/wiki/Pell%27s_equation" rel="noopener noreferrer" target="_blank">Pell equation</a>
<code>x^2 - 2*y^2 = -1</code>. The fundamental solution is <code>(x, y) = (1, 1)</code>, which
corresponds to the trivial arrangement <code>n = 1, b = 1</code>. From any solution the next is
obtained by composing with the fundamental solution <code>(3, 2)</code> of the companion equation
<code>X^2 - 2*Y^2 = +1</code>. Worked out in matrix form, this gives the
<a class="reference-source" href="https://en.wikipedia.org/wiki/Recurrence_relation" rel="noopener noreferrer" target="_blank">recurrence relation</a>:
</p>
<p>
<code>x' = 3x + 4y</code><br/>
<code>y' = 2x + 3y</code>
</p>
<p>
I start at <code>(x, y) = (1, 1)</code> and apply the step in a loop. After each step I recover the
disc counts with <code>n = (x + 1) / 2</code> and <code>b = (y + 1) / 2</code>. These divisions are
exact because <code>x</code> and <code>y</code> stay odd at every step - a parity that the
recurrence preserves from odd starting values (each new value is an even multiple plus an odd
multiple of two odd numbers, hence odd). The loop stops and returns <code>b</code> as soon as
<code>n</code> first meets or exceeds the target total.
</p>
<p>
The two implementations are line-for-line equivalent. The chief language-specific difference is
integer handling: Python uses arbitrary-precision integers automatically, while C declares
<code>long long</code> (64-bit signed) explicitly. Since the answer <code>756872327473</code> and
its corresponding total comfortably fit within 64 bits, the C version is safe with no big-integer
machinery. The second difference is in how the recurrence step is written: Python uses a single
tuple assignment, whereas C introduces two temporaries (<code>nx</code>, <code>ny</code>) so that
the new <code>x</code> does not clobber the old <code>x</code> before <code>y</code> is computed.
</p>
</article>