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

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

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

Головоломка 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.

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

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

В строке 200 мы знаем, что цепочка а пройдена полностью, и исследованы все символы, не являющиеся пробелами. Если в цепочке b содержится еще какой-нибудь символ, не являющийся пробелом, то равенства цепочек нет. Все в порядке.

В строке 300 цепочка а пройдена вплоть до некоторого символа, не являющегося пробелом, и этот символ еще не исследован. Цепочка b пройдена полностью, и в ней не содержится более ни одного символа, не являющегося пробелом. Следовательно, эти две цепочки различны. Можно было бы сказать, что дальнейшее движение по цепочке а бесполезно, но не приводит к ошибке. Но это неверно. Вы остановились на еще не исследованном символе, который не является пробелом. Если вы перейдете к следующему символу, не являющемуся пробелом, то данный символ вы потеряете. Если, как бывает в большинстве случаев, цепочка а совпадает с цепочкой b с точностью до пробелов за исключением единственного дополнительного символа в конце цепочки, то именно по этой-то причине и должен быть остановлен пробег цепочки а. Перемещаясь и не обнаруживая больше символов, не являющихся пробелами, мы получаем сообщение, что цепочки совпадают, а это неверно. Ясно, что программисты не принимали во внимание и не изучали именно этот случай. И никаких оснований поступать так нет. В этом и состоит преимущество логических рассуждений о тексте программы по сравнению с проверкой ее правильности с помощью тестирования.