Что такое Игра с вычитанием?
Игра с вычитанием — это ним с ограничением на каждый ход. Вы по-прежнему берёте предметы из одной кучи на выбор, но не меньше одного и не больше k, где k равно 2, 3, 4 или 5 и выбирается в настройках стола (по умолчанию 3). Взять кучу целиком можно, только если в ней k предметов или меньше.
Всё остальное как в стандартной игре: начальные кучи задаются той же опцией настроек (по умолчанию 1, 3, 5 и 7), а переключатель мизера решает, проигрывает ли взявший последний предмет (здесь по умолчанию) или выигрывает. Ограничение меняет арифметику игры. Большую кучу больше нельзя опустошить одним ходом, поэтому ею не поправишь позицию одним ударом, а значение каждой кучи определяет остаток от деления её размера на k + 1.
Изменения правил
| Правило | Ним (стандарт) | Игра с вычитанием |
|---|---|---|
| Ходы | Ним (стандарт)Возьмите один или несколько предметов из одной кучи, сколько угодно, вплоть до всей кучи. | Игра с вычитаниемВозьмите не меньше 1 и не больше k предметов из одной кучи; k равно 2, 3, 4 или 5 и выбирается в настройках стола (по умолчанию 3). |
| Кучи | Ним (стандарт)Несколько куч: по умолчанию 1, 3, 5 и 7 предметов или другой набор, выбранный в настройках стола. | Игра с вычитаниемТе же кучи, выбранные той же опцией. |
| Цель | Ним (стандарт)По умолчанию мизер: кто возьмёт последний предмет, проигрывает. В настройках можно переключиться на обычную игру, где взявший последний предмет побеждает. | Игра с вычитаниемТо же, с тем же переключателем мизера. |
| Выигрышная игра | Ним (стандарт)Обычная игра: оставляйте кучи с ним-суммой (побитовым XOR их размеров), равной нулю. Мизер: то же, пока не остались бы только кучи по одному предмету; тогда оставьте их нечётное число. | Игра с вычитаниемОбычная игра: каждая куча считается как остаток от деления её размера на k + 1, и вы оставляете эти остатки с ним-суммой, равной нулю; одиночная куча проиграна для того, кто ходит, ровно тогда, когда её размер кратен k + 1. Мизер: одиночная куча проиграна для того, кто ходит, ровно тогда, когда её размер на один больше числа, кратного k + 1. |
История
Счётные игры с ограничением на ход очень стары. В книге Клода-Гаспара Баше де Мезириака Problèmes plaisants et délectables, сборнике математических развлечений, впервые изданном в Париже в 1612 году, описана игра, в которой двое по очереди прибавляют к общей сумме число от 1 до 10, и побеждает тот, кто первым дойдёт до 100. Выигрышный план — занимать суммы 12, 23, 34 и так далее до 89, с шагом 11: та же арифметика, что и в одной куче из 100 предметов, из которой каждый ход берёт от 1 до 10.
Сам ним получил название и полную теорию от Чарльза Л. Бутона в 1901 году. Работы Роланда Шпрага (1935) и Патрика Гранди (1939) показали, что любая игра такого рода, включая игру с вычитанием, ведёт себя как куча нима определённого размера, и именно так решается вариант с несколькими кучами. Игры с вычитанием — стандартный пример в теории комбинаторных игр, например в книге Winning Ways for your Mathematical Plays Элвина Берлекэмпа, Джона Конвея и Ричарда Гая.