Math
Ним и двоичная сумма
Кучи камней, а под ними их двоичная запись. Разряд, в котором единиц нечётное число, горит красным; когда красных нет, ходящий уже проиграл. Правило проверено разбором всей игры, а не пересказано.
Что происходит
Бери сколько угодно камней из одной кучи; проигрывает тот, кому брать нечего. Под кучами карточка рисует их двоичную запись, столбик на кучу, и разряд с нечётным числом единиц горит красным. Утверждение Бутона: позиция проигрышна для ходящего ровно тогда, когда красных разрядов нет — когда двоичная сумма равна нулю. Верить на слово не предлагается: каждая позиция пространства состояний размечена разбором игры до конца, и метки сверены с правилом на 729, 2197, 4096 и 7776 позициях — расхождений ноль. Чтобы оставить противнику ноль, надо погасить красные столбцы, а сделать это может только куча, у которой в старшем красном разряде стоит единица. Таких куч нечётное число — иначе разряд не был бы красным, — поэтому выигрывающих ходов один или три и никогда два; счёт по трём кучам это подтверждает: 1092 позиции с одним ходом, 148 с тремя и ни одной с двумя. Включи мизер, где взявший последний камень проигрывает, и то же правило ломается: разбор расходится с ним ровно на позициях из одних единиц.
Уравнения модуля
Уравнения кучи камней, ход состоит в том, чтобы взять любое число камней из ОДНОЙ кучи, и проигрывает тот, кому нечего брать правило Бутона: позиция проигрышна для игрока, который должен ходить, тогда и только тогда, когда двоичная сумма (побитовое исключающее ИЛИ) размеров куч равна нулю карточка не ссылается на это правило - она размечает КАЖДУЮ позицию, решая игру до конца, и сравнивает: 729, 2197, 4096 и 7776 позиций, ноль расхождений выигрышные ходы - это кучи, для которых (h исключающее ИЛИ s) < h, и их число ВСЕГДА НЕЧЁТНО - одно или три, никогда не два: для трёх куч до 10 распределение такое: 0 ходов в 91 позиции, 1 ход в 1092, 3 хода в 148, а 2 хода - ни в одной причина не случайна: ход, обнуляющий сумму, делает куча, у которой в старшем установленном бите суммы стоит единица, и таких куч нечётное число, иначе этот бит суммы был бы нулевым проигрышные позиции подсчитаны точно: k куч с размерами 0..2^b−1 содержат их 2^(b(k−1)) - 64 для трёх куч размером 0..7 МИЗЕР - другая игра, и это правило в ней НЕВЕРНО: решение дерева расходится с исключающим ИЛИ ровно на 2^k позициях, и все они составлены из одиночных камней правило мизера: пока в какой-то куче больше одного камня, играйте как обычно; когда в каждой куче по одному камню, позиция проигрышна для ходящего тогда и только тогда, когда число куч НЕЧЁТНО (1,1,1) выигрышна для ходящего в обычной игре и проигрышна в мизере; (1,1) - наоборот; (2,1,1) выигрышна в обеих исходная раздача 7-5-3 имеет двоичную сумму 1 и ровно три выигрышных хода: в 6-5-3, в 7-4-3 и в 7-5-2
