Программирование игр и головоломок

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

Игра 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.

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

6. Комбинаторные задачи

Головоломка 28.

Действительно ли вам что-то еще нужно сообщать? Тогда я немного уточню способ поддержания части от 1 до р в порядке неубывания. Исходим ив упорядоченного по неубыванию вектора a₁, a₂, …, а_р. Вы последовательно заменяете элемент а_р элементами а_i, где i направлен по убыванию. Вы последовательно получите

a₁, a₂, …, а_р-1, а_р,

a₁, a₂, …, а_р, а_р-1,

a₁, a₂, …, а_р-3, а_р-1, а_р, а_{р- 2}.

По индукции, предположим, что в некоторый момент вы получили

a₁, …, а_{i- 1}, а_i+1, …, а_р, а_i

после перемены мест элементов с номерами i, р.

На следующем ходе вы поменяете местами а_{i- 1} и последний член, который равен а_i. Эта форма остается неизменной, и первая часть, от 1 до р ? 1, остается отсортированной в неубывающем порядке. В конце вы получите

a₂, a₃, …, а_р, a₁.

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

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