Жак Арсак - Программирование игр и головоломок
2 3 5 7 11 13 17 23 25 29
Счастливые числа — не обязательно простыв, а простые числа — не обязательно счастливые…
??? Головоломка 7. Дьявольская последовательность.
Марк Твен описал в своих рассказах жуткую историю. Человек прочел глупые стихи вроде
Кондуктор, отправляясь в путь,
Не рви билеты как-нибудь,
Стриги как можно осторожней.
Чтоб видел пассажир дорожный:
Синий стоит восемь центов,
Желтый стоит девять центов,
Красный стоит только три.
Осторожней режь, смотри!
Припев:
Режьте, братцы, режьте! Режьте осторожно!
Режьте, чтобы видел пассажир дорожный!
(Я цитирую по памяти, но дух соблюден.) Он был порабощен ритмом этих стихов, что стало настоящим наваждением. Если он начинал писать, его перо выводило «Режьте, братцы, режьте». Если он встречал кого-нибудь, он не здоровался с ним, а говорил «Режьте, братцы».
Он пробовал управлять собой, но это подрывало его здоровье. Он решил обратиться к своему священнику и объяснить ему, в чем дело, и читал ему это маленькое стихотворение, подчеркивая его ритм, пока пастор не выучил его наизусть. Ушел он исцеленный.
Но в воскресенье пастор начал проповедь словами «Режьте, братцы, режьте». Что бы ни было в гимне, который он запевал, слова были одни — «Режьте, братцы, режьте…» Его жизнь стала адом. Он не мог исцелиться, пока в один прекрасный день ему не удалось злодейски обучить этому стихотворению одного профессора университета…
Нижеследующее и есть «режьте, братцы, режьте». Оно преследует меня долгие годы. Я потерял массу времени на размышления о нем без сколько-нибудь значительного успеха. Но ничто меня не занимает в большей степени. Моя единственная надежда освободиться от него — это то, что вы им заинтересуетесь…
Последовательность определяется следующим образом: первый член этой последовательности есть произвольное нечетное число, отличное от единицы. Следующее за числом p равно
p/2, если p четно,
Зp + 1, если p нечетно.
Последовательность заканчивается, когда в ней встречается значение 1.
Вот последовательность, которую мы получим, исходя из 7:
7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
Нет никакой надежды, что вам удастся доказать, что для любого нечетного числа в качестве начального значения последовательность достигает единицы.
Но в высшей степени увлекательно составить эту крошечную программу и посмотреть, как она работает. Испытайте число 27 в качестве начального значения: вы получите очень длинную последовательность, среди элементов которой есть 9232. Если вы изучите ряды чисел, получаемые для начальных значений, взятых среди нечетных целых от 3 до 99, вы получите довольно много патологических последовательностей, не всегда сильно отличающихся. Все это очень смущает. Ни один специалист по теории чисел еще не смог Доказать, что такая последовательность принимает значение 1 для любого начального значения. Не больше известно и о том, почему некоторые из этих последовательностей — короткие, а другие — слишком длинные…
Эта программа замечательно иллюстрирует то, что называется «проблемой остановки». Существуют простейшие программы, относительно которых нет уверенности, что они остановятся…
Теперь, когда вы уже познакомились с этой последовательностью, получите предмет головоломки. Заметим сначала, что если p нечетно, то мы переходим к Зp + 1 — числу, отличному от 1. Очевидно, что непосредственно предшествующий шаг есть деление на 2. Поэтому можно изменить правило построения последовательности описанным ниже образом: следующее за числом p равно
p/2, если p четно,
(Зp + 1)/2, если p нечетно,
Это вычеркивает некоторые члены предыдущей последовательности, не меняя проблемы остановки:
7 11 17 26 13 90 10 5 8 4 2 1
Вы можете пойти еще дальше в том же направлении, объединяя вместе все последовательные шаги, действующие по правилу (Зp + 1)/2, и все следующие за ними шаги, состоящие в делении на два. Вы получите два новых правила перехода, гораздо более уплотненные. Свяжите их и пустите в ход. Для числа 7 вы должны без задержки получить последовательность
7 13 5 1
Это позволяет рассматривать обобщения задачи. Пусть k — нечетное число. Возьмем в качестве правил перехода следующие:
p/2, если p четно,
k * p + k − 2, если p нечетно.
Возможно уплотнение, аналогичное предыдущему. Для k = 5 следующее за числом 3 есть 3, и существуют исходные точки, для которых программа не останавливается. Для k = 7 она идет точно так же. Так что проблема остановки связана со свойством числа k. Я бы здесь… Впрочем, мало ли чего я хочу!
Зашифрованные операции
Это — класс самых разнообразных задач. Задаются точные арифметические операции, в которых некоторые цифры либо стерты, либо заменены буквами. В данной операции одна и та же буква всегда заменяет одну и ту же цифру, и разные буквы представляют поэтому разные цифры. Нужно восстановить исходную операцию. Есть случаи, в которых это сводится к решению системы уравнений с неизвестными, представляющими собой букву, — системы, решение которой дает также решение исходной задачи. Компьютер не видит ничего скрытного. Таким образом, если что-то не так, то нужно действовать систематически методом проб и ошибок. Нужно выбрать значения для одних букв и получить с их помощью значения остальных. Нужно проверить, что разным буквам соответствуют разные значения. После конечного числа попыток мы получим решение — если оно единственно — или список всех возможных решений. А еще существуют промежуточные решения: вычисление ограничивает число осуществляемых попыток.
Головоломка 8. SEND MORE MONEY.[4]
Это — лаконичная телеграмма английского студента своему отцу. История умалчивает о том, как отец это принял и были ли отправлены деньги…
SEND + MORE = MONEY
Программа очень легкая. Время вычисления короткое. Едва ли это головоломка. Как раз для тренировки…
Головоломка 9. HELP THE YOUNG.[5]
Конечно, конечно. Почему бы не послать им еще денег? Та же задача:
HELP + THE = YOUNG
Отметим разницу с предыдущей задачей. Предыдущая использовала не все цифры от 0 до 9. В этой участвуют все. Можете ли вы воспользоваться этим?
DEVOIR, LEÇON, ÉLÈVE.[6]
Есть аналогичные зашифрованные сложения по-французски. Например, такая:
ÉLÈVE + LEÇON = DEVOIR
? Головоломка 10. Зашифрованное умножение.
Довольно сложений, это становится скучным. Вот зашифрованное умножение:
ABCDE * 9 = FGHIJ
Здесь 10 букв представляют 10 различных цифр, так что одна из них равна 9. Можно сразу кое-что сказать о возможных значениях букв, но чтобы получить решение, придется идти буквально ощупью. Столько же придется искать и компьютеру.
?* Головоломка 11. Забавное число.
Число 123456789 обладает забавными свойствами:
123456789 * 2 = 246913578
Как и исходное, удвоенное число образовано всеми девятью цифрами, кроме 0.
123456789 * 4 = 493827156
Результат снова образован девятью цифрами, отличными от 0.
123456789 * 5 = 617283945
По-прежнему 9 цифр.
123456789 * 7 = 864197523
Опять 9 цифр, и это еще не все.
123456789 * 8 = 987654312
Но это не работает ни для 3, ни для 6. Это не может работать и для 9, потому что в результате больше 9 цифр,
Тем не менее есть много чисел, образованных всеми 9 цифрами (кроме 0), которые после умножения на 3 дают результат, образованный теми же девятью цифрами. Можете ли вы дать список всех таких чисел, оканчивающихся на 9? И также список тех, которые кончаются на 3?
Можно ли распространить использованный метод на случай умножения на 6?
Доказательства теорем
Компьютер можно использовать для доказательства теорем. Это — трудная задача искусственного интеллекта. Мы снабжаем компьютер правилами вывода, даем формулировку того, что требуется доказать, и исходные аксиомы. Компьютер пытается найти последовательность правил вывода, которые могут привести от исходных данных к требуемым рёзультатам.
Здесь обо всем этом речь не идет. Я предлагаю вам только взглянуть на путь, использованный для доказательства с помощью компьютера знаменитой проблемы четырех красок: любая географическая карта может быть раскрашена четырьмя красками так, что любые две территории, имеющие общую границу, раскрашены, разными красками. Общая идея состоит в том, чтобы доказать вручную или, в случае необходимости, с помощью программы, что проблема будет решена полностью, если будет известно ее решение в некотором конечном числе случаев. Эти случаи исследуются на компьютере. Вот примеры, доступные этому методу.
Внимание: вы должны бороться с проблемой сложности. Если вы не будете принимать никаких мер предосторожности, число подлежащих исследованию случаев может сказаться невероятно большим и работа компьютера станет невозможной: ведь перед вами не вечность… Равновесие между подготовительной работой (доказательством палых теорем) и работой компьютера оценивается в зависимости от ваших возможностей, одновременно в области математических доказательств и в ресурсах вашего микрокомпьютера. К сожалению, не говорите: эта программа отнимает уйму времени, я перепишу ее на ассемблере. Это — худшее из решений. Все, что я вам предлагаю, осуществимо на Бейсике за разумное время. Если ваша программа требует уйму времени, значит, она плохо придумана.
