В этой точке

у = 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 до р в порядке неубывания. Исходим ив упорядоченного по неубыванию вектора a1, a2, …, ар. Вы последовательно заменяете элемент ар элементами аi, где i направлен по убыванию. Вы последовательно получите

a1, a2, …, ар– 1, ар,

a1, a2, …, ар, ар– 1,

a1, a2, …, ар– 3, ар– 1, ар, ар– 2.

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

a1, …, аi– 1, аi+1, …, ар, аi

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

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

a2, a3, …, ар, a1.

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

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

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