Игра 22.

Вот шкала весов, предложенная А.-П. де Лоашем в книге Шварца [SCHJ:

0: отрезок замыкает проигрывающий треугольник,

1: отрезок замыкает треугольник, две стороны которого принадлежат моему противнику,

2: отрезок замыкает смешанный треугольник (одна из сторон которого — моя, а другая — моего противника),

3: отрезок соединяет две смешанных вершины (из каждой из них выходит и моя сторона, и сторона моего противника),

4: отрезок соединяет смешанную вершину и вершину, из которой выходит только одна сторона,

5: отрезок соединяет две вершины, каждая из которых принадлежит только одному отрезку, который провел именно я,

6: отрезок соединяет две вершины, каждая из которых принадлежит только одному отрезку, один из которых провел я, а другой — мой противник,

7: отрезок соединяет две вершины, которые не принадлежат проведенным мною отрезкам,

8: отрезок проходит через «чистую» (еще не использованную) вершину,

9: отрезок соединяет чистую вершину с вершиной, не принадлежащей моим отрезкам,

10: отрезок соединяет две чистые вершины.

Можно немного упростить этот список, не увеличивая сколько-нибудь серьезно опасность проиграть.

Игра 23.

Мы приводим список выигрывающих позиций, подразумевая при этом, что если S (р, q) выигрывает, то выигрывает и S (р, q') для всех q', не превосходящих q. Выберем, для каждого р наибольшее возможное для него значение q.

3,1 5,2 8,3 11,1 13,6 16,1 18,2

21,10 24,1 26,2 29,3 32,1

34,16 37,1 39,2 42,3 44,1 47,6 50,1

Игра 24.

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

Для каждой новой комбинации предложение некоторого цвета в некоторой позиции ведет к следующему:

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

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

Поэтому вы можете немедленно остановить испытание с цветом x в положении i, если:

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

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

либо она дает слишком много белых шашек,

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

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

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

Игра 27.

Рассмотрим игру НАДЕВАТЬ. В начале на игровом поле ничего нет. Можно играть только на поле, которое следует эа первым занятым полем, а такого поля нет. Играем на поле 1.

На следующем ходе было бы глупо снимать только что выставленную шашку. Первое занятое поле — первое. Ставим шашку на поле 2. Первое занятое поле — это снова первое поле. Было бы глупо снимать только что выставленную шашку, и поэтому нужно играть на первом поле, т. е. освобождать его. Теперь первое свободное поле — это поле 2. Было бы глупо возвращать на поле 1 только что снятую шашку. Следовательно, поставим шашку на поле 3. Никакого выбора…

Чтобы освободить игру на одно поле, очищаем поле 1.

Чтобы освободить игру на два поля, мы не можем очистить поле 1, так как тогда мы не могли бы очистить и поле 2. Первое занятое поле — поле 1. Можно очистить поле 2, а затем поле 1.

Для игры с 3 полями, мы очищаем 1, эатем ставим 3, ставим снова 1, очищаем 2, а затем 1.

Если n четно, то мы начинаем с удаления шашки 2, в противном случае мы удаляем шашку 1.

Теперь вам не составит ни малейшего труда написать итеративную программу:

Для игры СНИМАТЬ вы действуете аналогично.

В том, что касается последовательностей чисел, порожденных игрой СНИМАТЬ, начнем с рассмотрения конкретного примера. Вот игра СНИМАТЬ для n = 4.

Использованы все числа, меньшие 8, а из больших или равных 8 участвуют только 12, 13 и 15. Для обобщения действуйте по индукции.

Игра 29.

Вот решение для 8 букв и 10 полей.

..абабабаб

баабаба..б

бааб..аабб

б..баааабб

ббббаааа..

Присутствие куска X не меняет последовательности изменений.

..абабХабаб

баабабХа..б

бааб..Хаабб

б..бааХаабб

ббббааХаа..

Последний перенос пары букв аа слева от X в свободные пары справа дает

бббб..Хаааа

Теперь вы можете заняться X (если для этой комбинации вам решение уже известно) и получить

ббббY ..аааа

Таким образом, остается переместить два а с крайних полей справа на свободные поля, и все закончено. Следовательно, если вы умеете исследовать комбинацию Х с р парами букв а, б, то вы умеете исследовать и комбинацию с р + 4 парами.

Я уже предложил вам решение для четырех пар. Таким образом вы получаете решение для 8, 12,…

Главные решения — это решения для 4, 5, 6, 7 пар. Вот одно из решений для строчки из 5 пар