Жак Арсак - Программирование игр и головоломок

— выигрывающей позиции вы сопоставляете 0;

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

Образуем числа Спрага-Грюнди для этой игры.

Позиции 0 сопоставляется число 0, SG (0) = 0.

Исходя из 1, можно получить 0 (поскольку мы имеем право удалить одну спичку [19] Важно и то, что никаких других позиций, кроме 0, из 1 получить нельзя. — Примеч. ред. . Следовательно, SG(1) — наименьшее неотрицательное целое, отличное от 0, или SG(1) = 1. Исходя из 2, можно получить 1 и 0. Следовательно, SG(2) — наименьшее неотрицательное целое, отличное от 0 и 1, поэтому SG(2) = 2.

Так как можно удалять спички вплоть до 6, то точно так же имеем

SG(3) = 3, SG(4) = 4, SG(5) = 5, SG(6) = 6.

Предположим теперь, что имеется 7 спичек. Можно удалить от 1 до 6. Поэтому в результате можно получить от 6 до 1 спичек, но не 0. Число SG(7) — наименьшее неотрицательное целое, отличное от 1, 2, 3, 4, 5, 6, Следовательно, это 0.

SG(7) = 0,

А теперь из 8 можно получить от 2 до 7, поэтому SG(8) — это не 2, не 3, …, не 6 и не 0, поэтому оно равно 1.

SG(8) = 1.

Теперь вы можете установить общий закон:

SG( p ) = остаток от деления p на 7.

Как же выигрывать?

Если вы после своего хода можете оставить кучу, для которой число Спрага-Грюнди равно 0, то ваш противник не сможет достичь ситуации с числом нуль, поскольку по определению число, которое он оставит, отлично от исходного числа. Поскольку он не сможет достичь ситуации p с SG ( p ) = 0, то он и не может выиграть. Ему придется оставить вам ситуацию с SG( p ) ≠ 0, исходя из которой, вы всегда сможете получить ситуацию с числом Спрага-Грюнди, равным нулю. Следовательно, вам нужно оставлять вашему противнику число спичек с числом SG, равным нулю, иначе говоря, число спичек, кратное 7.

Одно из двух: либо ваш противник не знает этого правила и играет «по нюху»; при первой возможности вы оставляете ему кратное 7 и из ежовых рукавиц не выпускаете; либо он знает правило и ходит первым: он достигает кратного 7. Вы не сможете выиграть, если он не рассеян или не сделает ошибки в счете. Но компьютер не рассеян и не делает ошибок в счете (если ваша программа верна)…

Игра 17.

Выигрывающее положение — 31 декабря. Возьмите листок бумаги в клетку. Расположите по абсциссе месяцы, а по ординате дни. Так как 31 декабря выигрывает, то вы обозначаете эту точку числом Спрага-Грюнди 0. Из каждого дня декабря можно получить 31, но также и любой другой последующий день. Поэтому вы приписываете значение 1 дате 30 декабря, значение 2 дате 29 декабря, и т, д. То же для любого 31 числа; из него можно получить 31 число всех последующих месяцев. Поэтому 31 октября получает 1, 31 августа 2 и т. д.

После этого вы можете закончить значение таблицы и приписать число Спрага-Грюнди всем дням года. Вы увидите также появление дней со значением 0, которые являются выигрывающими днями. Напоминаю вам правило: каждому игровому положению приписывается наименьшее неотрицательное целое значение, отличное от значений тех положений, которые можно получить, исходя из данного, т. е. в настоящем случае — от значений тех положений, которые расположены правее, и тех, которые расположены ниже.

Закон заполнения таблицы достаточно сложен; и я не пытаюсь вам его сформулировать. Как только октябрь заполнен, появляется простая закономерность, которая дает соотношение между номером дня и номером месяца для выигрывающих положений.

Даже если вы мало знаете современную математику, вы слышали разговоры об отношении эквивалентности. Все выигрывающие положения эквивалентны. Игровое положение задается парой д , м , где д — номер дня, а м — номер месяца. Следовательно, вы должны найти такое отношение эквивалентности для пар натуральных чисел, чтобы

д , м ' было не эквивалентно д , м при м ≠ м ', и

д ', м было не эквивалентно д , м при д ≠ д '.

Наконец, для выигрывающей позиции д , м должно быть эквивалентно 31, 12. Что-то похожее на это можно видеть в программах лицеев…

Я прекрасно понимаю, что календарь осложняет все, поскольку длина месяца не постоянна и зависит от м , причем к тому же с непростым законом изменения. Но, к счастью, оказывается, что это никак не сказывается на этом замечательном отношении эквивалентности.

После всего сказанного вы должны выпутаться из этой задачи…