Программирование игр и головоломок - [72]

со стержня 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.

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

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₁.

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

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

Процедура работает достаточно быстро для того, чтобы в случае неудачи иметь возможность испытать наличие решения для 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.

Для задачи

9 7 6 4 3 1 n = 795 через 6 с получается

4 * 9 = 36, 36 + 1 = 37, 37 * 7 = 259,

259 + 6 = 265, 265 * 3 = 795.

Наконец,

100 50 8 5 4 2 n = 631.

За менее чем 2 с получаем

50 − 4 = 46 , 46 * 2 = 92, 92 * 8 = 736,

100 + 5 = 105 , 736 − 105 = 631.

Я уже предлагал вам следующий пример:

100 75 50 25 10 10.

Для n = 370 особой трудности нет, потому что это — кратное десяти.

Компьютер сообщает мне

75/25 = 3,

50 − 3 = 47,

47 * 10 = 470,

470 − 100 = 370.

Это уже интересно, потому что это — совершенно не то решение, которое я собирался искать.

Чтобы найти 369, нужно образовать число, не кратное 5, — чего нельзя сделать с помощью какой-либо из трех операций +, −, *, сохраняющих кратность пяти. Следовательно, нужно использовать деление. Вот решение: