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

Арсак Жак

В этой точке

у = 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, — чего нельзя сделать с помощью какой-либо из трех операций +, -, *, сохраняющих кратность пяти. Следовательно, нужно использовать деление. Вот решение:

50/10 = 5,

5 * 75 = 375,

375 - 10 = 365,

100/25 = 4,

365 + 4 = 369.

Обе представленные здесь программы не позволяют получить это решение. Действительно, оно записывается в виде

(50/10) * 75 + 100/25 - 10.

А число 368? Вы нашли для него решение? Я не сумел. Но Жак Бейгбеде сообщил мне, что он получил его делением на 25…

10 * 100= 1000,

1000 - 75 = 925,

925 * 10 = 9250,

9250 - 50 = 9200,

9200/25 = 368.

7. Обо всем понемногу

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