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

Игра 36.

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

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

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

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

a 1, a 2, …, а р -1, а р ,

a 1, a 2, …, а р , а р -1,

a 1, a 2, …, а р -3, а р -1, а р , а р -2.

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

a 1, …, а i -1, а i +1, …, а р , а i

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

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

a 2, a 3, …, а р , a 1.

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

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

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

— решение, если оно существует,

— приближение о точностью до единицы, если это возможно.

Эта программа терпит неудачу крайне редко.

В выпуске от 8 марта 1984 года следующий розыгрыш не был найден ни кандидатами, ни Бертраном, ни кем- либо из присутствующих:

50 10 10 5 4 2 n = 767.

На моем микрокомпьютере нужно 18 с, чтобы обнаружить, что эта задача не имеет решения, а затем еще 5 с, чтобы получить

50 − 10 = 40 , 40 * 5 = 200, 10 − 2 = 8,

200 − 8 = 192, 192 * 4 = 768.