После этого вы можете закончить значение таблицы и приписать число Спрага-Грюнди всем дням года. Вы увидите также появление дней со значением 0, которые являются выигрывающими днями. Напоминаю вам правило: каждому игровому положению приписывается наименьшее неотрицательное целое значение, отличное от значений тех положений, которые можно получить, исходя из данного, т. е. в настоящем случае — от значений тех положений, которые расположены правее, и тех, которые расположены ниже.
Закон заполнения таблицы достаточно сложен; и я не пытаюсь вам его сформулировать. Как только октябрь заполнен, появляется простая закономерность, которая дает соотношение между номером дня и номером месяца для выигрывающих положений.
Даже если вы мало знаете современную математику, вы слышали разговоры об отношении эквивалентности. Все выигрывающие положения эквивалентны. Игровое положение задается парой д, м, где д — номер дня, а м — номер месяца. Следовательно, вы должны найти такое отношение эквивалентности для пар натуральных чисел, чтобы
д, м' было не эквивалентно д, м при м ≠ м', и
д', м было не эквивалентно д, м при д ≠ д'.
Наконец, для выигрывающей позиции д, м должно быть эквивалентно 31, 12. Что-то похожее на это можно видеть в программах лицеев…
Я прекрасно понимаю, что календарь осложняет все, поскольку длина месяца не постоянна и зависит от м, причем к тому же с непростым законом изменения. Но, к счастью, оказывается, что это никак не сказывается на этом замечательном отношении эквивалентности.
После всего сказанного вы должны выпутаться из этой задачи…
Игра 18.
Эта игра — производная от средневековой игры. Сначала попытайтесь достичь 50 с точностью до кратного 7. Но как только все четыре карты, имеющие одинаковое значение, оказываются использованными, так ситуация сразу меняется. Вот пример начала партии,
Я беру туза, компьютер тоже. Сумма 2.
Чтобы получить 8, я беру 6. Компьютер берет туза. Сумма 9.
Чтобы получить 15, я снова беру 6.
Компьютер берет последнего туза. Сумма 16,
Теперь остаются следующие карты:
2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 5 6 6
Так как тузов больше нет, то числа Спрага-Грюнди изменились[20]. Теперь из 49 больше нельзя получить 50.
SG(50) = 0, SG(49) = 0.
Из (48) можно получить 50. Поэтому SG(48) = 1.
Из 47 можно получить 49 и 50, но не 48. Поэтому SG(47) = 1.
Теперь положения, имеющие нулевое SG, — это
42 41 34 33 26 25 18 17
Поэтому я могу взять 2, чтобы достичь 18.
Стратегия усложняется, поскольку числа Спрага-Грюнди полностью меняются при удалении каждой карты. Но это как раз и благоприятствует компьютеру. Если он не может достичь выигрывающего положения, он берет карту, оставшуюся в наименьшем количестве экземпляров. Каждый раз, когда тот или иной тип карт исчерпывается, компьютер пересчитывает заново числа Спрага-Грюнди.
Мне придется переписать мою программу в соответствии с этой стратегией.
Игра 19. Ним-сумма.
Для меня эта игра — своего рода педагогический вызов. Я чрезвычайно раздражен тем, что все, кто излагает эту игру, ведут себя одинаково: известно, что выигрывающей стратегией является следующая… Почему она выигрывает? Откуда она вообще взялась эта стратегия?
Выписать числа Спрага-Грюнди очень трудно.
Попытаемся найти несколько выигрывающих положений.
Если к моменту своего хода я обнаруживаю только одну спичку, то я выигрываю.
Если я обнаруживаю единственную кучку, то я тоже выигрываю.
Если, кроме одной кучки, ничего больше нет, то можно положить SG(0) = 0 (я выигрываю, я взял последнюю спичку), вследствие чего SG(n) = n.
Предположим теперь, что у нас две кучки. Если я оставляю две кучки, в каждой из которых по одной спичке, то я обязательно выигрываю: мой противник должен взять столько спичек, сколько он хочет, но — только из одной кучки. У него нет выбора, он может только взять одну из спичек, после чего я возьму последнюю спичку и выиграю.
Если я оставляю две одинаковые кучки по n спичек в каждой, то у моего противника две возможности:
— взять целиком одну из кучек, я возьму другую и выиграю;
— взять часть одной из кучек и оставить в ней n' спичек. Я возьму столько же из другой, оставляя ситуацию n', n'. По индукции — я на пути к победе.
20
Читатель может вернуться к определению чисел Спрага-Грюнди и убедиться, что эти числа определяются на множестве игровых позиций раз и навсегда, исходя из правил игры, и, разумеется, не могут меняться в процессе разыгрывания конкретной партии. Что же является позицией в этой средневековой игре? — Позицией является состав выложенных на стол карт, а также их значения: сколько карт на столе имеет значение 1, сколько карт имеет значение 2, и т. д. Сумма, набранная игроками в данный момент, равна 84 минус сумма значений карт на столе. Что же имеет в виду автор книги, когда он пишет SG(50)? Почему он приписывает число Спрага-Грюнди не позиции, а сумме карт этой позиции? Дело в том, что для всех позиций с набранной суммой 50 число Спрага-Грюнди одинаково и равно 0. Это и позволяет написать равенство SG(50) = 0. А что могло бы значить SG(49)? Если бы все позиции с суммой 49 имели одинаковое число SG, мы бы обозначили его SG(49). Но, увы! Разные позиции с суммой 49 имеют разные числа Спрага-Грюнди. Так что автор книги дальше рассуждает о несуществующих вещах. Я из этих рассуждений ничего полезного извлечь не смог (кроме подозрения, что у автора нет работающей программы, играющей в 24 карты). —