Игра Уайтхоффа

Две кучи размеров $a$ и $b$. Ход — взять любое положительное число камней из одной кучи либо поровну из обеих. Проигрывает тот, кто не может сходить, то есть тот, кому досталась позиция $(0, 0)$.

Та же игра часто описывается как ферзь на доске: фигура ходит влево, вниз и по диагонали влево-вниз, цель — угол. Координаты клетки и есть размеры куч.

Проигрышные позиции

Первые несколько (с точностью до перестановки):

$$(0,0),\ (1,2),\ (3,5),\ (4,7),\ (6,10),\ (8,13),\ (9,15),\ (11,18),\ (12,20),\ \ldots$$

Закономерность видно по разностям: они идут $0, 1, 2, 3, 4, \ldots$ подряд. А меньшие числа пар — это $0, 1, 3, 4, 6, 8, 9, 11, 12$: в точности те, которые ещё не встречались.

Отсюда способ построить таблицу без всякой теории: идти по $k = 0, 1, 2, \ldots$, брать наименьшее неиспользованное число $a_k$ и объявлять пару $(a_k,\ a_k + k)$ проигрышной. Для $a, b \le 10^5$ этого достаточно.

Формула

Те же пары выражаются через золотое сечение $\varphi = \frac{1 + \sqrt 5}{2}$:

$$(\lfloor k\varphi \rfloor,\ \lfloor k\varphi \rfloor + k), \qquad k = 0, 1, 2, \ldots$$

Проверено перебором: на всей доске $301 \times 301$ множество проигрышных клеток совпало с формулой без исключений.

Как проверять позицию, не строя таблицу

Пусть $a \le b$ и $k = b - a$. Позиция проигрышна ровно тогда, когда $a = \lfloor k\varphi \rfloor$.

Считать $\lfloor k\varphi \rfloor$ можно двумя способами, и стоит знать границы обоих.

Целочисленный — точен всегда, но упирается в разрядность: в произведении $5k^2$ при $k$ порядка $1{,}36 \cdot 10^9$ кончается 64-битное знаковое число.

long long isqrt(long long n) {                 // целочисленный корень
    long long x = (long long)std::sqrt((double)n);
    while (x > 0 && x * x > n) x--;            // подгонка обязательна:
    while ((x + 1) * (x + 1) <= n) x++;        // double промахивается на единицу
    return x;
}
bool losing(long long a, long long b) {
    if (a > b) std::swap(a, b);
    long long k = b - a;
    return a == (k + isqrt(5 * k * k)) / 2;
}

Через double — просто (long long)(k * PHI). Здесь ожидаемо подозрение на потерю точности, поэтому вот замер: сравнение с точной формулой на 300 000 подряд идущих $k$ в каждом диапазоне.

$k$ около	промахов из 300 000
$10^6$	0
$10^8$	0
$10^9$	0
$10^{10}$	1
$10^{12}$	53
$10^{15}$	53 796

Вывод получается не тот, которого ждёшь: до $10^9$ double не ошибается ни разу, а ломаться начинает там, где целочисленный вариант уже переполняется. Практически это значит, что при ограничениях до $10^9$ годятся оба, а за пределами $1{,}36 \cdot 10^9$ не годится ни один — там нужна 128-битная арифметика.

И всё же писать лучше целочисленный: он не требует ни этого замера, ни рассуждений о том, сколько разрядов осталось на дробную часть.

Почему нельзя просто сложить две кучи

Уайтхофф — не сумма двух игр: ход «взять поровну из обеих» меняет оба слагаемых сразу, а теорема Шпрага — Гранди такого не допускает. Поэтому XOR здесь неверен, и приходится разбирать игру отдельно.

Это полезный пример: как только в условии появляется ход, задевающий несколько частей позиции, разложение на сумму игр надо перепроверять.

Смежное

• Ним;
• Сумма игр.