Текст книги "Программирование игр и головоломок"

Автор книги: Жак Арсак

сообщить о нарушении

Текущая страница: 15 (всего у книги 16 страниц)

3. Игры без стратегии

Игра 13.

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

Я представил всю игру одной-единственной цепочкой символов с кодами возврата каретки, расположенными надлежащим образом – так, чтобы визуализация игры сводилась к визуализации этой цепочки бее какого-либо дополнительного исследования. Куры обозначаются в этой цепочке присвоенными им буквами, лисы – буквами X, пустые игровые поля обозначаются точками. Остальные символы (пробелы или возврат каретки) не отвечают никаким используемым игровым полям. Я добавил в начале и в конце по строчке пробелов, чтобы не было необходимости изучать возможность некоторых перемещений на границе игрового поля.

Я не храню положений лис с помощью двух переменных. Я отыскиваю их положение в цепочке, представляющей игру, с помощью функции «положение» языка LSE. Это – существенная деталь. Поиск наиболее длинного взятия я осуществляю итеративно. Я образую две цепочки:

– одна из них содержит список кур, уже взятых при исследовании данного пути (это – последовательность букв взятых кур),

– вторая цепочка содержит дуплеты: положение в игре и рассматриваемое направление (мы осуществляем взятие, исходя из положения x и двигаясь в направлении, обозначенном через i).

Находясь в положении x и в направлении i я смотрю, есть ли кура на поле x + d[i]. Если ее нет, то в этом направлении никакое взятие невозможно. Если же такая кура есть, то я смотрю, не содержится ли буква этой куры в цепочке уже взятых кур. Если содержится, то в этом направлении ничего не сделаешь. Если же эта кура еще не взята, то я проверяю, действительно ли поле x + 2 * d[i] содержит именно точку – в противном случае никакого взятия нет. Действуя таким образом, я не сталкиваюсь ни с какими трудностями на краях (там есть предохранительная строка, и она не содержит ни одной куры).

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

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

4. Игры со стратегией

Игра 19.

И здесь тоже решение неединственно. Вот одно из них, хорошо приспособленное к используемой мною машине, на которой деления на 2 не бесплатны (на мой взгляд, выполняются слишком долго). Нам известна верхняя граница числа спичек в каждой кучке, определяемая принятым вами правилом (я взял 4 кучки с по крайней мере 16 спичками). Я рассматриваю двоичные записи числа спичек в кучке, начиная слева. Я задаюсь числом p = 8. Если число больше или равно 8, то оно содержит 1 в крайнем левом из возможных положений. Тогда я вычитаю 8 из этого числа и перехожу к p = 4.

Сначала я определяю крайнюю левую цифру для числа спичек во всех четырех кучках. Из них я удерживаю только две вещи: четность этого числа (переменная q, вначале равная 0, изменяется на 1 – q при каждой встрече с единицей; результат нечетен, если в конце получается q = 1); номер последней встреченной кучки, у которой в данном положении встретилась единица. Я исследую таким образом все положения слева направо, пока не встречаю положение, для которого сумма единиц, стоящих в этом положении, нечетна. Тогда я знаю кучку (ту, номер которой был удержан в памяти), у которой в этом положении стоит именно единица. Я убираю из этой кучки желаемое число спичек, чтобы эта единица исчезла (8, если сейчас изучается крайнее левое положение).

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

Игра 20.

Я ничего не добавляю, потому что эта игра является вариантом нимской игры. На каждой строке есть пустые поля, играющие ту же роль, что и спички в кучках нимской игры. Единственная разница состоит в том, что игрок может отступать. Если вы можете достичь выигрывающей позиции (такой, что НИМ-сумма пустых полей между игроками на каждой строчке оказывается равной нулю) и если противник отступает одной из своих шашек, увеличивая число пустот на этой строке, то вы на столько же полей продвигаетесь вперед, восстанавливая таким образом предшествующую – и потому выигрывающую – ситуацию. Противник оказывается немного глубже вбитым в свой угол и приблизившимся к своей гибели. Если в какой-то момент все промежуточные пустые поля пропадут, то шашки оказываются рядом друг с другом, и ваш противник может только отступать. А вы за ним следуете…

Игра 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, если:

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

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

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

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

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

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

5. Стратегия без игры (выигрывающие стратегии)

Игра 27.

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

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

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

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

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

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

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

место := 0; игра : = пусто

ВЫПОЛНЯТЬ

  ЕСЛИ поле (1) = пусто ТО поставить (1);

    место := место + 1

  ИНАЧЕ удалить (1);

    место := место − 1

  КОНЕЦ_ЕСЛИ

  ЕСЛИ место = n ТО КОНЧЕНО КОНЕЦ_ЕСЛИ

  искать первое занятое поле, номер которого дает число i;

  ЕСЛИ поле (i + 1) = пусто ТО поставить (i + 1);

    место := место + 1

  ИНАЧЕ удалить (i + 1);

    место := место − 1

  КОНЕЦ_ЕСЛИ

  ЕСЛИ место = n ТО КОНЧЕНО КОНЕЦ_ЕСЛИ

ВЕРНУТЬСЯ

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

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

0001	1
0011	3
0010	2
0110	6
0111	7
0101	5
0100	4
1100	12
1101	13
1111	15

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

Игра 29.

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

..абабабаб

баабаба..б

бааб..аабб

б..баааабб

ббббаааа..

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

..абабХабаб

баабабХа..б

бааб..Хаабб

б..бааХаабб

ббббааХаа..

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

бббб..Хаааа

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

ббббY ..аааа

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

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

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

..абабабабаб

Искомое расположение имеет вид

бббббааааа..

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

..абабабабаб

баабабаба..б

бааб..абаабб

бааббаа..абб

б..ббааааабб

бббббааааа..

Предлагаю вам разыграть 6 и 7 пар. Совершенно бесполезно подключать к этому делу компьютер. А где же программирование, спросите вы? Я отвечу, что это упражнение вводит вас в рекурсивные или индуктивные рассуждения. Это оздоровляет Наши способы рассуждать…

Игра 30.

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

Игра имеет ту же конфигурацию, что и для лис и кур. Поле обозначается своим положением в цепочке. Перемещение в данном направлении реализуется добавлением некоторой константы к данному положению. Таблица из четырех элементов дает эти константы для всех четырех направлений. Свободное поле представляется точкой, занятое поле – крестиком ×.

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

Вы уже проделали более трудную работу для самого длинного взятия в игре с курами и лисами.

Игра 31.

Число ходов f(р) для переноса р дисков получается переносом сначала p − 1 дисков со стержня d на стержень 3 − а − d за f(р − 1) ход, затем из перемещения диска р, что требует в точности одного хода, а затем возвращения р − 1 дисков из запаса на стержень прибытия за f(р − 1) ход, откуда получаем:

f(р) = 2 * f(р − 1) + 1,

g(p) = f(p) + 1 = 2 * f(р − 1) + 2 = 2 * (f(p − 1) + 1) − 2 * g(р − 1).

По индукции g(р) = 2^pg(0).

Так как f(0) = 0, g(0) = f(0) + 1 = 1, g(р) = 2^p, то, наконец

f(р) = 2^p − 1.

Для игры с 50 дисками нужно 2⁵⁰ − 1 ходов. Но 2¹⁰ равно 1024, или порядка 10³. Следовательно, 2⁵⁰ порядка 10¹⁵.

В часе 3600 секунд, в сутках 3600 × 24 = 86400 секунд, за год получаем 86400 × 365 – или порядка 3 × 10⁷ секунд, откуда, наконец, 3 × 10⁹ секунд за столетие. Поэтому нужно порядка 10¹⁵/3 × 10⁹, или порядка 3 × 10⁵ веков для игры с 50 дисками, которая, таким образом, требует около 300000 веков…

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

Опыт показывает, что для первых значений n реализация игры Н(n, d, а) дает следующее;

– диски, попадающие в основание стержней d и а, имеют ту же четность, что и n,

– диски, попадающие в основание запасного стержня, имеют другую четность.

Предположим, что это свойство справедливо для n − 1. Для реализации Н(n, d, а) нужно выполнить сначала Н(n − 1, d, 3 − а − d). В течение этой операции диск n остается в основании начального стержня d и, следовательно, в основании диска d находится диск n и потому диск той же четности, что и n. Диски, которые при этом оказываются в основании стержня прибытия для процедуры Н(n − 1, d, 3 − а − d), имеют (по предположению индукции) ту же четность, что и n − 1. Но этот стержень прибытия является для игры Н(n, d, а) запасным стержнем, и, следовательно, в основании запасного стержня оказываются диски, имеющие ту же четность, что и n − 1. Наконец, запасной стержень для игры Н(n − 1, d, 3 − а − d) есть а, в основание которого попадают диски с четностью n − 2, следовательно, с четностью n.

Перемещение диска n со стержня d на стержень а помещает n в основание стержня а, так что при этом свойство четности для а подтверждается. Проверьте, что для стержней d и 3 − а − d оно также подтверждается. Для этого разложите Н (n, d, а) на 5 операций:

Н (n − 2, d, а) n и n − 1 на стержне d

Р (n − 1, d, 3 − а − d) n на d, n − 1 на 3 − а − d

Н (n − 2, а, 3 − а − d)

Р (n, d, а) n на а, n − 1 на 3 − а − d

Н (n − 2, 3 − a − d, d)

Р (n − 1, 3 − а − d, а) n на а, n − 1 на а

Н (n − 2, d, а).

Предположим, что искомое свойство четности выполняется для n − 1. Тогда остается заниматься только теми дисками, которые ложатся на диск n.

В первой операции диск n − 1 находится на диске n, они разной четности, и, таким образом, здесь свойство четности выполняется. Во время игры Н(n − 2, а, 3 − а − d) диск n находится на стержне, который для этой игры является запасным. Диски, которые в этой игре ложатся в основание этого стержня – и потому ложатся на диск n – имеют четность, противоположную четности числа n − 2, следовательно, четность, противоположную четности n, что и проверяет на этом этапе наше условие четности. Вы легко завершите это рассуждение.

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

Игра 33.

Предположите, что в Н (n − 1, d, а) диск 1 перемещается всегда в одном и том же направлении. Для Н (n, d, а) вы должны выполнить

Н (n − 1, d, 3 − а − d)

Н (n − 1, 3 − а − d, а).

Вместо того, чтобы непосредственно переходить от d к а, вы осуществляете этот переход с помощью стержня 3 − а − d, иначе говоря, вы делаете два перемещения в обратном направлении. Диск 1 продолжает перемещаться всегда в одном и том же направлении, но это направление меняется при переходе от n − 1 к n. Для n = 1 этот диск перемещается в направлении от d к а. Это всегда будет так для всех нечетных n, в то время как для четных n он будет перемещаться в направлении от а к d.

Простое итеративное решение имеет следующий вид: исходя ив четности n определите направление перемещения диска 1. Начните с 2ⁿ − 1 число ходов, которые осталось сделать:

s := ЕСЛИ четно (n) ТО 2 ИНАЧЕ 1 КОНЕЦ_ЕСЛИ

d := 0; k:= 2n − 1

ВЫПОЛНЯТЬ

  а := d + s; ЕСЛИ a > 2 ТО а := а − 8

  КОНЕЦ_ЕСЛИ

  переместить диск 1 с d на а;

  d : = a; k := k − 1

  ЕСЛИ k = 0 TO КОНЧЕНО КОНЕЦ_ЕСЛИ

  переместить единственный диск, который можно переместить, кроме диска 1

k := k − 1

ВЕРНУТЬСЯ

Все диски имеют общее свойство: нечетные диски перемещаются в том же направлении, что и диск 1, а четные диски – в другом направлении.

В вышеприведенной программе стратегия совершенна с точки зрения исполнения вручную, потому что в каждый данный момент сразу видно, какой диск нужно переместить, если это не самый маленький диск (меньший из двух остальных дисков перемещается на больший). В нашей программе вам нужно вычислить это движение. Один из наиболее простых способов состоит в том, чтобы представить игру с помощью вектора, дающего для диска i номер стержня, на котором он находится. Диск, подлежащий перемещению – это наименьший Диск, который находится не на том же стержне, что и диск 1, следовательно, номер стержня которого отличается от d. Этот самый диск перемещается со стержня, на котором он находится – с номером x – на стержень 3 − x − d.

Обозначим первое перемещение через 1. Поскольку диск 1 перемещается один раз в каждой паре ходов (точнее, перемещается через ход), то он перемещается в каждый нечетный ход. По индукции покажите, что диск p перемещается в ходы с номерами, которые делятся на 2^р−1, но не делятся на 2^p (т. е. являются нечетными кратными числа 2^p−1).

Номер k любого хода может быть единственным способом представлен в виде

k = (2r + 1)2^р-1.

Перемещаемый на этом ходе диск есть диск с номером p, и это – его (r + 1)-е перемещение. Так как он начинает движение со стержня 0 и перемещается в направлении s_p (1, если р нечетно, и 2 в противном случае), то на этом ходе диск перемещается с rs_p-го на (r + 1)s_р-й стержень, где эти числа берутся по модулю 3.

Игра 34.

Попытаемся охарактеризовать значение р, дающее игре оптимум для данного n. Нам известно, что f₃(n − p)= 2^n-p − 1.

Должно выполняться

2f₄(p − 1) + 2^n-p+1 − 1 ≥ 2f₄(р) + 2^n-p − 1,

2f₄(p + 1) + 2^n-p-1 − 1 ≥ 2f₄(р) + 2^n-p − 1.

Удобно пользоваться первыми разностями для функции f₄:

d(р) = f₄(p + 1) − f₄(p).

Два приведенных выше соотношения могут быть переписаны следующим образом:

d(p − 1) < 2^n-p-1, d(р) ≥ 2^n-p-2.

Интересно рассматривать даже не d(р), а скорее 2^pd(р) = g(р):

g(р − 1) ~ 2^n-2 ≤ g(р).

Можно еще упростить запись, беря не g(р), а величину

h(р) = log₂(g(р)) = р + Iog₂(d(р)).

Тогда получаем

h(р − 1) < n − 1 ≤ h(р).

При данном n величина р – наименьшее целое, для которого h больше или равно n − 2.

Приведем здесь первые из полученных таким образом значений:

n	q	f 4	p	d	h
0	0	0		1	0
1	1	1		2	2
2		3		2	3
3	2	5	1	4	5
4		9	1	4	6
5		13	1	4	7
6	3	17	3	8	9
7		25	3	8	10
8		33	4	8	11
9		41	5	8	12
10	4	49	6	16	14
11		65	6	16	15

Мы добавили в таблицу переменное q, связанное с «треугольными» числами. Для n = q(q + 1)/2 действительно убеждаемся, что

h(р) = h(р − 1) + 2

в то время как для других n

h(p) = h(p − 1) + 1.

Исходя из n, можно вычислить q:

q = целая_часть (( − 1)/2).

Имеем

h(n) = n + целая_часть (( − 1)/2).

Покажите это по индукции. Исходя отсюда, вычисляется все. Таким образом, если n дано, то р – наименьшее целое, большее или равное

(2n − 1 − )/2.

Игра 35.

Возьмем, например, игру с 50 дисками. Она реализуется переносом сначала 40 дисков на запасной стержень, а затем 10 последних дисков со стержня 0 на стержень 1, с использованием при этом только трех свободных стержней. Наконец, остается перенести начальные 40 самых маленьких дисков с запасного стержня на первый стержень, используя все 4 стержня.

Чтобы переместить 40 дисков с 4 стержнями, сводим задачу к перемещению 31 диска с 4 стержнями, а затем 9 с 3 стержнями…

Таким образом, дело сводится к разбиению 50 дисков на 8 сегментов:

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

Договоримся работать с тремя стержнями 0, 1, 2, так что стержень 3 остается пустым и служит запасным стержнем при любом перемещении какого-либо сегмента. Более точно, перемещение сегмента р со стержня d на стержень а осуществляется с помощью изученной выше процедуры Н, в которой запасным стержнем является стержень 3.

Сегмент 1 перемещается в каждый из двух ходов подряд (под ходом я понимаю последовательность операций, реализующих процедуру Н), всегда в одном и том же направлении.

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

Игра 36.

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

Предположим, что SG (p_i, 1) = 0.

Исходя из p_i + 1, я могу удалить 1 спичку и получить пару p_i, 1. Следовательно, SG (p_i + 1, q) ≠ 0.

Исходя из p_i + 2, я для любого q всегда могу удалить две спички, но тогда я получаю SG (p_i, 2) ≠ 0, и, следовательно,

SG (p_i + 2, 1) = 0.

Если в p_i имеем q_i > 1, то тогда мы этого не получим и SG (p_i + 2, 1) ≠ 0. Но в p_i + 3, удаляя единственную спичку, получаем пару p_i + 2, 1 c SG ≠ 0, или же, удаляя две спички, получаем пару p_i + 1, 2 с ненулевым числом SG. Следовательно, SG (p_i + 3, 1) = 0.

Все оставшееся уже очень хорошо подготовлено. Рассмотрите точку р, для которой диагональ пересекает ось р = 0, не пересекая положений с нулевым SG. Эта прямая задается уравнением x + у = р. Она пересекает ось x = 0 в точке у = р. Нельзя взять в точности р спичек, – можно не больше р − 1. Следовательно, в этой точке

q = целая_часть ((р − 1)/2).

Рассмотрим теперь точку, абсцисса которой есть число Фибоначчи: р = fib (s).

Нужно показать, что прямая x + у = fib (s) не пересекает точек с ненулевыми SG, кроме x = 0. Рассмотрим сначала точку

х = fib (s − 1).

В этой точке

у = fib (s) − fib (s − 1) = fib (s − 2).

При p = fib (s − 1)

q = целая_часть ((fib (s − 1) − 1)/2).

Нужно показать, что для каждого s

целая_часть ((fib (s − 1) − 1)/2) < fib (s − 2),

или, что равносильно,

fib (s − 1) < 2 * fib (s − 2) + 1.

Но

fib (s − 1) = fib (s − 2) + fib (s − 3)

и

fib (s − 3) < fib (s − 2).

Следовательно, рассматриваемая диагональ не пересекает точек с нулевым SG в fib (s − 1). Она не может пересекать их и между s − 1 и s, поскольку эта часть воспроизводит то, что происходит в интервале от 1 до fib (s − 2), а диагональ, выходящая из fib (s − 2), не пересекает точек с нулевым SG до оси q.

Вы без труда завершите это доказательство.