Problem 100: Arranged Probability

Mathematical Foundation

Theorem 1 (Diophantine formulation). The condition $\frac{b(b-1)}{n(n-1)} = \frac{1}{2}$ is equivalent to the Diophantine equation

Proof. Cross-multiplying: $2b(b-1) = n(n-1)$, i.e., $2b^2 - 2b = n^2 - n$. $\square$

Theorem 2 (Reduction to Pell’s equation). Under the substitution $x = 2b - 1$, $y = 2n - 1$, equation (1) transforms to

Proof. From (1): $2b^2 - 2b = n^2 - n$. With $b = (x+1)/2$ and $n = (y+1)/2$:

Remark. Equation (2) is the negative Pell equation $y^2 - 2x^2 = -1$. It has solutions because $\sqrt{2} = [1; \overline{2}]$ has an odd-length period in its continued fraction expansion.

Theorem 3 (Fundamental solution and recurrence). Equation $2x^2 - y^2 = 1$ has fundamental solution $(x_0, y_0) = (1, 1)$. All positive solutions are generated by

Proof. Verification that $(1,1)$ satisfies $2 \cdot 1 - 1 = 1$. For the recurrence, suppose $2x_k^2 - y_k^2 = 1$. Then:

The recurrence arises from multiplication in $\mathbb{Z}[\sqrt{2}]$: the fundamental solution to $y^2 - 2x^2 = -1$ corresponds to the unit $\alpha = 1 + \sqrt{2}$, and iterating $\alpha^{2k+1}$ generates all solutions to $y^2 - 2x^2 = -1$. The matrix form

corresponds to squaring the fundamental unit: $(1 + \sqrt{2})^2 = 3 + 2\sqrt{2}$, giving $x \to 3x + 2y$, $y \to 4x + 3y$.

Completeness (that all solutions arise this way) follows from the theory of Pell equations: the group of units of $\mathbb{Z}[\sqrt{2}]$ with norm $\pm 1$ is generated by $1 + \sqrt{2}$. $\square$

Theorem 4 (Integrality of $b$ and $n$). For each solution $(x_k, y_k)$ of (2), both $x_k$ and $y_k$ are odd, so $b = (x_k + 1)/2$ and $n = (y_k + 1)/2$ are positive integers.

Proof. By induction. Base: $x_0 = 1$ and $y_0 = 1$ are both odd. Inductive step: if $x_k$ and $y_k$ are odd, then $x_{k+1} = 3x_k + 2y_k = \text{odd} + \text{even} = \text{odd}$, and $y_{k+1} = 4x_k + 3y_k = \text{even} + \text{odd} = \text{odd}$. $\square$

Theorem 5 (Second-order recurrence for $b$ and $n$). The sequences $b_k$ and $n_k$ satisfy the second-order linear recurrence

with initial values $(b_0, n_0) = (1, 1)$ and $(b_1, n_1) = (3, 4)$.

Proof. From the matrix recurrence in Theorem 3, composing two steps of the $(x, y)$ recurrence and substituting $b = (x+1)/2$, $n = (y+1)/2$:

The characteristic equation of the matrix $M = \begin{pmatrix} 3 & 2 \\ 4 & 3 \end{pmatrix}$ is $\lambda^2 - 6\lambda + 1 = 0$ (trace $= 6$, determinant $= 1$). Therefore $x_{k+1} = 6x_k - x_{k-1}$ and $y_{k+1} = 6y_k - y_{k-1}$. Substituting $x_k = 2b_k - 1$:

The same derivation applies to $n_k$. Initial values: $(x_0, y_0) = (1, 1)$ gives $(b_0, n_0) = (1, 1)$; $(x_1, y_1) = (5, 7)$ gives $(b_1, n_1) = (3, 4)$. Verification: $2 \cdot 3 \cdot 2 = 12 = 4 \cdot 3$. $\square$

Verification.

Editorial

The probability condition is awkward in $(b,n)$ directly, but after the standard substitution it becomes a Pell-type equation. That means the valid arrangements do not need to be searched combinatorially; they appear as a recurrence sequence of exact solutions.

The implementation works entirely in the $(b,n)$ recurrence derived from the Pell equation. Starting from the first two nontrivial solutions, it repeatedly generates the next arrangement and stops when the total number of discs first exceeds $10^{12}$. So the search space is explored in the exact order of valid solutions, and no invalid pair is ever considered.

Pseudocode

Initialize the first two solutions of the blue-disc recurrence.

While the current total number of discs does not yet exceed the threshold:
    Compute the next blue-disc count from the recurrence
    Compute the next total-disc count from the same recurrence
    Shift the two-solution window forward

Return the current blue-disc count.

Complexity Analysis

Time: The eigenvalues of $M$ are $3 \pm 2\sqrt{2}$, so $n_k \sim (3 + 2\sqrt{2})^k$. The number of iterations to exceed threshold $T$ is $\lceil \log_{3+2\sqrt{2}} T \rceil = O(\log T)$. Each iteration is $O(1)$ (fixed-precision arithmetic suffices since $T = 10^{12} < 2^{40}$). Total: $O(\log T)$.

Space: $O(1)$.

Answer

#include <bits/stdc++.h>
using namespace std;

int main() {
    // 2b(b-1) = n(n-1) reduces to 2x^2 - y^2 = 1 (x=2b-1, y=2n-1).
    // Second-order recurrence: b' = 6b - b_prev - 2, n' = 6n - n_prev - 2.
    // Initial: (b0,n0)=(1,1), (b1,n1)=(3,4).

    const long long T = 1000000000000LL;
    long long bp = 1, np = 1;
    long long bc = 3, nc = 4;

    while (nc <= T) {
        long long bn = 6 * bc - bp - 2;
        long long nn = 6 * nc - np - 2;
        bp = bc; np = nc;
        bc = bn; nc = nn;
    }

    cout << bc << endl;
    return 0;
}

"""
Project Euler Problem 100: Arranged Probability

Find the number of blue discs b in the first arrangement with n > 10^12
total discs such that P(two blue) = b(b-1)/(n(n-1)) = 1/2.

The condition 2b(b-1) = n(n-1) reduces to the negative Pell equation
2x^2 - y^2 = 1 via x = 2b-1, y = 2n-1. The second-order recurrence
b_{k+1} = 6*b_k - b_{k-1} - 2 (and same for n) generates all solutions.

Answer: 756872327473
"""


def solve():
    threshold = 10**12

    b_prev, n_prev = 1, 1
    b_curr, n_curr = 3, 4

    while n_curr <= threshold:
        b_next = 6 * b_curr - b_prev - 2
        n_next = 6 * n_curr - n_prev - 2
        b_prev, n_prev = b_curr, n_curr
        b_curr, n_curr = b_next, n_next

    print(b_curr)


if __name__ == "__main__":
    solve()