xxxiv. Wythoff's Game

Problem. Two piles; a move removes any number from one pile, or the same number from both. Whoever cannot move loses.

Answer: the losing positions are $(\lfloor k\phi \rfloor ,\lfloor k{\phi }^2\rfloor )$ for $k\ge 0$, $\phi =\frac{1+\sqrt{5}}{2}$: $(0,0),(1,2),(3,5),(4,7),(6,10),(8,13),\dots$ In each pair the difference is $k$.

bool wythoffLosing(long long a, long long b) {    // P-position iff smaller = floor(k * phi), k = difference
    if (a > b) swap(a, b);
    long long k = b - a, s = sqrtl((long double)5 * k * k);
    while (s * s > 5 * k * k) s--; while ((s + 1) * (s + 1) <= 5 * k * k) s++;
    return a == (k + s) / 2;                      // floor(k * (1 + sqrt 5) / 2)
}

Proof: the losing positions

Define $a_k=\mathrm{mex}\{a_j,b_j:j<k\}$ and $b_k=a_k+k$. These pairs are exactly the P-positions: from $(a_k,b_k)$, a single-pile move changes one coordinate and yields no pair (each number occurs in exactly one pair), and a diagonal move keeps the difference $k$, which belongs only to pair $k$. From any other position $(x,y)$, $x\le y$: if $x=a_k$ with $y>b_k$, move to $(a_k,b_k)$; if $x=b_k$, move the other pile to $a_k$; otherwise $x=a_k$ with $y<b_k$, and the diagonal move to $(a_j,b_j)$ with $j=y-x<k$ exists. Finally, $a_k=\lfloor k\phi \rfloor$, $b_k=\lfloor k{\phi }^2\rfloor$ by Beatty’s theorem ($\frac{1}{\phi }+\frac{1}{{\phi }^2}=1$, so these sequences partition the positive integers). The code computes $\lfloor k\phi \rfloor =\lfloor (k+\sqrt{5k^2})/2\rfloor$ with an exact integer square root. Checked against the game DP for piles below 80.