Почему важен двоичный «остаток» кучек
Речь о классической игре ним: за ход игрок забирает любое положительное число спичек, но только из одной кучки. Обычно выигрывает тот, кто забирает последнюю спичку. Чтобы найти сильный ход, размеры кучек записывают в двоичной системе — как числа, состоящие из нулей и единиц, — а затем складывают их поразрядно без переносов. Такая операция называется исключающим ИЛИ, или XOR: одинаковые биты дают 0, разные — 1.
Например, для кучек размером 3, 4 и 5 двоичные записи выглядят так: 011, 100 и 101. Их XOR равен 010, то есть 2. Это число называют ним-суммой.
Как из вычисления получается ход
Если ним-сумма не равна нулю, можно изменить одну кучку так, чтобы после хода она стала равна XOR этой кучки с ним-суммой. В примере кучку из 3 спичек можно уменьшить до 1: число 3 XOR 2 равно 1. После этого размеры кучек — 1, 4 и 5, а их ним-сумма уже равна нулю.
Почему это работает? При ненулевой ним-сумме найдётся кучка, которую можно уменьшить до нужного размера: в её двоичной записи достаточно изменить некоторые единицы на нули. Уменьшение одной кучки разрешено правилами, а значит, вычисление сразу подсказывает законный ход.
Что означает нулевая ним-сумма
При идеальной игре позиция с ним-суммой 0 не даёт игроку хода, который сохранит ноль: любой ход оставит сопернику ненулевую ним-сумму. Тот, в свою очередь, может вернуть её к нулю. Поэтому игрок, получивший такую позицию, может проиграть при безошибочной игре; ненулевая ним-сумма, напротив, даёт способ перевести соперника в неё.
Так несколько кучек превращаются в задачу на биты: стратегия состоит не в том, чтобы брать как можно больше спичек, а в том, чтобы после своего хода оставить двоичный остаток, равный нулю.
