Приключения Коли Герасимова и Фимы Королёва (джен)

Итак, маленький золотой ключик, который Коля Герасимов нашел в кармане костюма Наполеона Бонапарта, подошел к левой двери "Махагона". Коля повернул ключ в замке и открыл дверь. Мальчики вошли внутрь левого отделения шкафа. Тумблер, как они и ожидали, был в положении Л, т. е устройство работало в режиме лифта. Фима взялся за тумблер и переключил его сначала в положение М, т. е. в режим метро. На табло, которое было под тумблером, зажглась надпись красными буквами: Пользоваться СОМВ в режиме М категорически запрещено до особого распоряжения. За нарушение — штраф 100 рублей!

Следует напомнить, что сто рублей в 1984 г. было весьма большой суммой.

Затем Фима перевел тумблер в положение В, т. е. в режим машины времени. Надпись на табло погасла, но по рации раздался властный голос Фомы Остаповича:

— Молодые люди, не забудьте снять костюмы. Покрасовались, и хватит! Но конверт возьмите с собой — он вам еще пригодится. И не забудьте закрыть обе двери шкафа.

Мальчики повиновались — вышли из левого отделения шкафа, закрыли его дверь маленьким золотым ключиком, сняли костюмы, повесили их на вешалки в правом отделении шкафа, его дверь закрыли серебряным ключом, а ключи и конверт Фима положил в карман своей куртки. После этого Коля и Фима пошли к столбику с пультом управления и встали в круг.

Фима нажал на маленькую квадратную белую кнопку с цифрой 0. По рации раздались пять коротких отрывистых звуковых сигналов, на панели управления загорелся индикатор "Пуск", кнопки с цифрами от 1 до 9 перелились всеми цветами радуги, а дверь кабины СОМВ с музыкальным звуком закрылась. После этого Фима нажал на красную кнопку с цифрой 1, расположенную в нижней части пульта управления. В нижней части пульта загорелся индикатор "Исходная станция", а кнопки с цифрами от 1 до 9 вновь перелились всеми цветами радуги. С помощью белых кнопок с цифрами от 0 до 9 Фима набрал дату и время назначения: 13.09.2084, 16:00:00, а затем нажал на красную кнопку с цифрой 2. Загорелся индикатор "Конечная станция", кнопки с цифрами от 1 до 9 в третий раз перелились всеми цветами радуги, и Фома Остапович приказал:

— Встаньте в круг!

Убедившись в том, что они уже стоят в круге, мальчики хором ответили:

— Уже стоим!

Фома Остапович отдал им новый приказ:

— Возьмитесь за поручни!

Осмотревшись по сторонам и не увидев никаких поручней, Коля и Фима, начисто забыв о своём предшествующем опыте использования данного устройства, с удивлением спросили:

— Где?

В этот момент из боковых сторон столбика выскочили два металлических поручня, и мальчики крепко взялись за них своими руками. Фома Остапович приказал им:

— Закройте глаза!

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

— Дышите глубоко! — таков был следующий приказ Фомы Остаповича.

Мальчикам пришлось сделать серию глубоких вдохов. Но в это время ими снова одолело любопытство, и Фима открыл правый, а Коля (о, Боже! — какая непозволительная дерзость!) — левый глаз. Мальчики посмотрели вперёд и не обнаружили никаких новых изменений в кабине СОМВ.

Но Фома Остапович сердито рявкнул на них:

— Сколько раз повторять, не подглядывайте! Ведь вы не первый раз пользуетесь этой машиной!

— Ничего не поделаешь, придется повиноваться и немножко потерпеть — подумали при этом Коля и Фима и покорно закрыли глаза, опять пожав при этом плечами.

По своему опыту (бóльшей частью — горькому) мальчики ожидали, что теперь в кабине СОМВ должен погаснуть свет, в результате чего она погрузится в кромешную тьму. Но неожиданно по рации раздался новый приказ Фомы Остаповича:

— Откройте глаза и введите пароль!

Мальчики открыли глаза и хором вскрикнули:

— Какой пароль?!

Фома Остапович сказал:

— В соответствии с распоряжением Управления внутренних дел Свердловского района города Москвы, доступ к режиму машины времени ограничен. К путешествиям во времени допускаются только те, кто знает пароль. Пароль представляет собой натуральное число, состоящее не более, чем из десяти цифр, которое набирается с помощью белых кнопок с цифрами от 0 до 9. После окончания набора пароля следует вновь нажать на красную кнопку с цифрой 2 в нижней строке пульта управления.

— Новая напасть! — недовольно буркнул Фима и набрал наугад первый попавшийся пароль:

1234567890

Пароль высветился синими цифрами в третьей строке табло на пульте управления, под текущими и желаемыми датой и временем. После этого Фима нажал на красную кнопку с цифрой 2. Мальчики услышали, что внутри пульта началось какое-то шуршание, продолжавшееся около минуты, после чего Фома Остапович произнес:

— Пароль нейтрален. Не блокирую машину времени и возвращаю ее в исходное состояние. Закройте глаза и не подглядывайте!

Пожав плечами, Коля и Фима сделали кислые мины на своих лицах и закрыли глаза. Еще через минуту по рации раздался голос Фомы Остаповича:

— Переброска завершена! Счастливого пути! И не забудьте распечатать конверт и прочесть письмо!

Дверь кабины СОМВ с музыкальным звуком открылась. Открыв глаза, мальчики увидели, что на пульте управления горит индикатор "Переброска закончена", а на табло текущие дата и время — 13.09.1984, 16:15:00 (указанные зелеными цифрами) далеко не совпадают с датой и временем назначения — 13.09.2084, 16:00:00 (указанными красными цифрами). Коля и Фима сняли руки с поручней (они сразу же задвинулись внутрь столбика), сошли с круга и направились к выходу из кабины СОМВ.

— Постой! — сказал Фима. — Распечатаем конверт и прочтем письмо, так сказать, не отходя от кассы. Может быть, там указан правильный пароль?

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

Ограничение доступа к режиму машины времени в СОМВ

В соответствии с распоряжением Управления внутренних дел Свердловского района города Москвы, доступ к режиму машины времени в СОМВ ограничен. К путешествиям во времени допускаются только те, кто знает пароль. Пароль представляет собой натуральное число, состоящее не более, чем из десяти цифр, которое набирается с помощью белых кнопок с цифрами от 0 до 9. После окончания набора пароля следует вновь нажать на красную кнопку с цифрой 2 в нижней строке пульта управления. Пароль, обеспечивающий доступ к режиму машины времени в СОМВ, определяется по следующим правилам:

1. Множество допустимых паролей образовано натуральными числами, состоящими не более, чем из десяти цифр. Таким образом, минимальное допустимое значение пароля равно 1, а максимальное — 9 999 999 999.

2. На множестве допустимых паролей определена функция f, которая может принимать значения на множестве целых неотрицательных чисел. Таким образом, минимальное возможное значение функции f равно 0, а максимальное — не ограничено.

3. Следует учитывать, что 0 является целым, но не является натуральным числом. Поэтому, в соответствии с пп. 1 и 2, 0 не входит в область определения функции f, но входит в область ее значений.

4. Если x является натуральным числом, состоящим не менее, чем из трех, но не более, чем из десяти цифр, причем первая и последняя цифры числа x равны 2, то значение функции f(x) получается удалением начальной и конечной двоек из числа x. Например, f(252) = 5, f(283612) = 8361, f(2123452) = 12345.

5. Если f(x) = y, то значение функции f от числа, получаемого добавлением слева к числу x цифры 4, получается добавлением слева к числу y цифры 2. В частности, в соответствии с примерами п. 4, f(4252) = 25, f(4283612) = 28361, f(42123452) = 212345.

6. Если f(x) = y, то значение функции f от числа, получаемого добавлением слева к числу x цифры 6, равно числу, получаемому цифрами числа y, записанными в обратном порядке. В частности, в соответствии с примерами пп. 4 и 5, f(6252) = 5, f(64252) = 52, f(6283612) = 1638, f(642123452) = 543212.

7. Если f(x) = y, то значение функции f от числа, получаемого добавлением слева к числу x цифры 8, равно числу, получаемому цифрами числа y, повторенными дважды. В частности, в соответствии с примерами пп. 4 и 5, f(8252) = 55, f(84252) = 2525, f(86283612) = 16381638, f(8642123452) = 543212543212.

8. Если для некоторого числа x, принадлежащего области определения функции f, не удается применить ни одно из правил пп. 4 — 7, то f(x) = 0. В частности, f(1) = 0, f(1984) = 0, f(12345678) = 0. Кроме того, ноль может получиться и в результате применения п. 4: f(202) = 0. На основании указанных примеров, в результате применения пп. 5 и 7 имеем: f(41) = f(4202) = f(41984) = f(412345678) = 20; f(841) = f(84202) = f(841984) = f(8412345678) = 2020.

9. Если в результате применения пп. 4 и 6, в качестве значения функции f(x) получается число, не равное нулю, но начинающееся с одного или нескольких нулей, то они удаляются. В частности, f(2022) = 02 = 2, f(6428360002) = 0006382 = 6382. Если же в результате применения пп. 4 и 7 получается число, состоящее из нескольких нулей, то оно заменяется одним нулем: f(20002) = 000 = 0; f(81984) = 00 = 0.

10. Если x — некоторое допустимое значение пароля, то возможны четыре случая:

1) Пароль x обеспечивает доступ к путешествиям во времени из прошлого в будущее, но блокирует доступ к путешествиям из будущего в прошлое. Такой пароль существует, и притом только один. В результате использования данного пароля попытка совершить путешествие из прошлого в будущее увенчается полным успехом, а попытка совершить путешествие из будущего в прошлое приведет к тому, что режим машины времени в СОМВ будет навсегда заблокирован.

2) Пароль x обеспечивает доступ к путешествиям во времени из будущего в прошлое, но блокирует доступ к путешествиям из прошлого в будущее. Такой пароль также существует, и притом только один. Значение данного пароля меньше, чем значение пароля, указанного в п. 1). В результате использования данного пароля попытка совершить путешествие из будущего в прошлое увенчается полным успехом, а попытка совершить путешествие из прошлого в будущее приведет к тому, что режим машины времени в СОМВ будет навсегда заблокирован.

3) Пароль x нейтрален. Таких паролей — немногим менее 50% от числа всех допустимых паролей. В результате использования данного пароля попытка совершить путешествие во времени (в любом направлении) окончится неудачей, но режим машины времени в СОМВ не будет заблокирован.

4) Пароль x — блокирующий. Таких паролей — также немногим менее 50% от числа всех допустимых паролей. В результате использования данного пароля попытка совершить путешествие во времени (в любом направлении) также окончится неудачей, а режим машины времени в СОМВ будет навсегда заблокирован.

11. Если x и y — некоторые допустимые значения пароля, причем f(x) = y, то:

1) если пароль x нейтрален, то пароль y — блокирующий;

2) если пароль x — блокирующий, то пароль y нейтрален.

12. Если в течение месяца, т. е. до 17:00:00 13.10.1984, ни один пассажир СОМВ не введет ни одного из паролей, указанных в пп. 10. 1) и 10. 2), то режим машины времени в СОМВ будет навсегда заблокирован.

С уважением, к. ф.-м. н., доц. Павел Игнатьевич Полоскóв

МГУ, мехмат, кафедра теории вероятностей и математической статистики

Желаю удачи!

— Да ... — не скрывая досады, произнес Коля. Требуемые пароли существуют и единственны, но нам не то, чтобы за месяц, а и за сто лет их не отгадать.

— А если будем искать подбором, так машину вообще навсегда заблокируют. Можно будет пользоваться ей только как лифтом, — добавил Фима. — Впрочем, идея! Едем к доценту Полоскову, ведь это, наверное, он разработал систему блокировки.

— К дедушке Павлу? — спросил Коля.

— Ну он пока еще не дедушка, а только дядюшка, — ответил Фима. — Ему только тридцать два года.

Мальчики вышли из кабины СОМВ (совсем забыв, что ей можно было воспользоваться как лифтом и подняться на первый этаж). Кирпичная стена с музыкальным звуком закрылась, и красная кнопка рядом с ней погасла. Фима открыл медным ключом дверь будки. Мальчики вышли из нее, и Фима запер дверь. Пройдя через колонный зал и поднявшись по лестнице на первый этаж, Коля и Фима вышли на улицу через "парадную" дверь с большой восьмеркой (которая теперь была оборудована домофоном). После этого мальчики пошли к станции метро "Проспект Мира" и приехали на станцию "Университет" (естественно, при этом они не сами управляли поездами Кольцевой и Кировско-Фрунзенской линий — поезда, как и положено, вели машинисты, а Коля и Фима сидели в вагоне). Пройдя по улице, мальчики вошли в тридцатитрехэтажное здание МГУ на Ленинских горах. Фима спросил у дежурного:

— Доцент Полосков с кафедры теории вероятностей Мехмата здесь?

Дежурный ответил:

— Сейчас позвоню по местному телефону и выясню это.

Выяснив в таблице подразделений номер кафедры теории вероятностей и математической статистики факультета Мехмат, дежурный позвонил по данному номеру и спросил:

— Доцент Полосков сейчас на кафедре?

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

Поблагодарив дежурного, мальчики поехали домой, а на следующий день, 14 сентября, после обеда, вновь приехали в МГУ. На этот раз доцент Полосков был на кафедре и с радостью принял мальчиков. Фима объяснил Павлу Игнатьевичу суть проблемы и попросил его помочь ее решить. В первую очередь Павел Игнатьевич обратил внимание мальчиков на следующее обстоятельство:

— Сказано ли в одиннадцатом правиле, что пароль y непременно должен отличаться от пароля х?

Коля задумался и через четверть минуты сказал:

— Не знаю... Во всяком случае, явно об этом не сказано.

Фима добавил:

— Ну раз не сказано, значит, по-видимому, эти пароли вполне могут совпадать.

— Совершенно верно, — сказал Павел Игнатьевич. — Одиннадцатое правило вполне допускает случай совпадения паролей х и y. Иными словами, вполне допусти́м случай, когда пароль y — это тот же самый пароль х. Если мы заме́ним в формулировке одиннадцатого правила пароль y на пароль x, то как тогда будет читаться данное правило?

Коля подумал и сказал:

— Если x и x — некоторые допустимые значения пароля, причем f(x) = x, то:

1) если пароль x нейтрален, то пароль x — блокирующий;

2) если пароль x — блокирующий, то пароль x нейтрален.

— Но ведь не может же пароль x быть и нейтральным, и блокирующим одновременно! — воскликнул Фима.

— Правильно, — ответил Павел Игнатьевич. — Если x — такой пароль, что значение функции f от него равно самому себе, то и в случае, когда пароль x нейтрален, и в случае, когда он блокирующий, мы приходим к противоречию. Значит, оба случая исключены, и такой пароль может только... — здесь Павел Игнатьевич сделал паузу, желая дать договорить мальчикам.

— ... открывать доступ к путешествиям во времени, либо вперед, либо назад! — с радостной интонацией закончил Фима.

— Но как найти такое значение пароля x? — спросил Коля.

— Для этого нам нужно познакомиться с такой важной категорией функций, как рекурсивные функции, — ответил Павел Игнатьевич. — Но сначала нужно найти ответ на вопрос: сколько решений должно иметь уравнение f(x) = x?

Коля задумался, а Фима смог дать ответ:

— В соответствии с пунктами 1 и 2 десятого правила, два. Причем бо́льшее из них дает пароль, открывающий доступ к путешествиям в будущее, а меньшее — к путешествиям в прошлое.

— Молодец, Фима! — похвалил мальчика Павел Игнатьевич. — А теперь перейдем к рекурсивным функциям. Слышали ли вы о числах Фибоначчи?

— Конечно! — ответил Коля. — Это числа 1, 1, 2, 3, 5, 8, 13 и так далее.

— Совершенно верно, — сказал Павел Игнатьевич. — А по какому правилу они определяются?

— Ряд Фибоначчи начинается с двух единиц, а каждое число, начиная с третьего, равно сумме двух предыдущих, — ответил Фима.

— Да, это так, — согласился Павел Игнатьевич. — А теперь определим функцию f(n), областью определения которой является множество натуральных чисел, а значением — число Фибоначчи с порядковым номером n. Тогда f(1) = f(2) = 1; f(3) = 2; f(4) = 3; f(5) = 5; f(6) = 8; f(7) = 13 и т. д. Правила, определяющие данную функцию, можно сформулировать следующим образом: f(1) = f(2) = 1; f(n) = f(n — 1) + f(n — 2) при n >= 3. Первое правило — обычное, а второе — рекуррентное, т. е. определяющее значение функции через одно или несколько значений той же функции от меньших значений аргумента. Функция, использующая в своем определении одно или несколько рекуррентных правил, и называется рекурсивной функцией. Итак, функция, определяющая ряд Фибоначчи, является рекурсивной функцией.

— Рекурсивными являются также функции суммы и произведения двух натуральных чисел, — продолжал Павел Игнатьевич. — Например, если f(x, y) = x + y, то f(1, 1) = 2; f(x, y) = f(x, y — 1) + 1 при y > 1; f(x, y) = f(x — 1, y) + 1 при x > 1, а если f(x, y) = xy, то f(1, 1) = 1; f(x, y) = f(x, y — 1) + x при y > 1; f(x, y) = f(x — 1, y) + y при x > 1. Весьма сложной рекурсивной функцией является функция Аккермана: f(x, y) = y + 1 при x = 0; f(x, y) = f(x — 1, 1) при x > 0, y = 0; f(x, y) = f (x — 1, f (x, y — 1) при x > 0, y > 0.

В этот момент Павел Игнатьевич запустил на ЭВМ, стоявшей у стены, программу для вычисления значения функции Аккермана, и ввел в нее значения аргументов: 4; 4. Примерно через полминуты программа выдала сообщение о переполнении. Действительно, значение функции Аккермана от двух четверок, равное 2 ^ (2 ^ (2 ^ 65536)) — 3, настолько велико, что количество цифр в данном числе значительно превосходит количество атомов в наблюдаемой части Вселенной.

— А теперь ответьте на вопрос: является ли функция f, определенная на множестве допустимых значений пароля, рекурсивной? — спросил Павел Игнатьевич.

С минуту подумав, Фима ответил:

— Да, является. Правила 4, 8 и 9 — обычные, но правила 5, 6 и 7 — рекуррентные.

— Совершенно верно, — сказал Павел Игнатьевич. Итак, мы установили, что на множестве допустимых значений пароля определена рекурсивная функция f, причем уравнение f(x) = x имеет два решения, меньшее из которых дает пароль, открывающий доступ к путешествиям в прошлое, а бо́льший — в будущее. Но сейчас уже поздно, нам пора прощаться. Поэтому к следующей нашей встрече постарайтесь найти ответы на вопросы:

1. Можно ли найти решения исследуемого уравнения, используя только обычные правила определения функции f?

2. Если ответ на первый вопрос отрицательный, то какие именно рекурсивные правила необходимо использовать, чтобы найти решения, и в каком порядке их следует применять?

3. Каким образом можно найти решения уравнения и доказать, что других решений не существует?

Коля и Фима поблагодарили Павла Игнатьевича за интересную беседу, попрощались с ним и поехали домой. В течение последующих двадцати семи дней, по 11 октября включительно, мальчики бились над поставленными вопросами, но смогли лишь доказать, что ответ на первый вопрос — отрицательный. Действительно, для того, чтобы было f(x) = x, необходимо (хотя и не достаточно), чтобы количество цифр в числе f(x) было равно количеству цифр в числе x. Однако по правилу 4 в числе x на две цифры меньше, чем в числе f(x). Правило 9 еще сильнее уменьшает количество цифр в значении функции f, а правило 8 позволяет добиться равенства количества цифр в аргументе и в значении функции только для однозначных значений аргумента. Однако добиться равенства значений аргумента и функции по данному правилу не получится: 0 не входит в область определения функции f, поэтому значение аргумента должно быть больше нуля, а значение функции по данному правилу равно нулю.

У мальчиков осталось менее двух суток на решение данной проблемы, ведь если никто так и не сможет ввести правильного пароля, то в пять часов пополудни 13 октября режим машины времени в СОМВ будет навсегда заблокирован. Однако накануне рокового дня, 12 октября, произошло одно из тех событий, которые кардинально изменяют ход истории: в школе № 20 г. Москвы состоялась олимпиада по математике. Естественно, что Коля и Фима приняли в ней участие. Одна из задач олимпиады как раз и была связана с рекурсивными функциями:

На множестве натуральных чисел определена функция f, которая может принимать значения на множестве целых неотрицательных чисел. Значение функции f определяется по правилам:

1. Если x является натуральным числом, начинающимся с цифры 2 и состоящим не менее, чем из двух цифр, то значение функции f(x) получается удалением двойки из числа x. Например, f(253) = 53, f(2836) = 836, f(212345) = 12345.

2. Если f(x) = y, то значение функции f от числа, получаемого добавлением слева к числу x цифры 3, получается добавлением справа к числу y цифры 2, за которой еще раз повторяются цифры числа x. В частности, в соответствии с примерами п. 1, f(3253) = 53253, f(32836) = 8362836, f(3212345) = 12345212345, f(332836) = 836283628362836.

3. Если для некоторого числа x, принадлежащего области определения функции f, не удается применить ни одно из правил пп. 1 и 2, то f(x) = 0. В частности, f(1) = 0, f(529) = 0, f(1984) = 0. Кроме того, ноль может получиться и в результате применения п. 1: f(20) = 0.

4. Если в результате применения пп. 1 и 2, в качестве значения функции f(x) получается число, не равное нулю, но начинающееся с одного или нескольких нулей, то они удаляются. В частности, f(2022) = 022 = 22, f(20005718) = 0005718 = 5718, f(31) = 020 = 20.

Требуется найти все решения уравнения f(x) = x и доказать, что других решений нет.

Коля не смог решить данную задачу, а Фима смог. Прежде всего, как и для задачи определения пароля к СОМВ, Фима понял, что обычные правила 1, 3 и 4, без использования рекуррентного правила 2, не позволяют найти решение данной задачи: по правилу 1 значение функции будет иметь на одну цифру меньше, чем ее аргумент, а по правилу 3 — не сможет совпасть с ним, т. к. 0 не входит в область определения функции. Правило 4 еще сильнее сокращает количество цифр результата. Однако рекуррентное правило 2 увеличивает количество цифр результата функции от аргумента, начинающегося с тройки, на одну единицу более чем в два раза по сравнению с количеством цифр значения функции от аргумента без тройки. Если k — количество цифр некоторого числа x, начинающегося с двойки, то f(x) будет содержать (k — 1) цифру, а значение функции f от числа, получаемого добавлением слева к числу x цифры 3 (оно содержит (k + 1) цифру) — (2 * (k — 1) + 1) = (2k — 1) цифру. Для равенства аргумента и значения функции необходимо равенство количества цифр, поэтому k + 1 = 2k — 1, откуда k = 2. Итак, число x содержит две цифры, причем первая из них равна двум (и других вариантов быть не может). Обозначим вторую цифру числа x буквой a. Тогда x = (2a), где скобки означают число, состоящее из двух цифр — 2 и a (а не 2, умноженное на a). По правилу 1 f(x) = f((2a)) = a, а по правилу 2 — f((3x)) = f((32a)) = (a2a). Для того, чтобы f(x) = x, необходимо и достаточно, чтобы (32a) = (a2a), откуда a = 3 и (32a) = (a2a) = (323). Итак, f(323) = 323, и число 323 является единственным решением данной задачи.

Действительно, по правилу 1 f(23) = 3 и по правилу 2 f(323) = 323.

Вернувшись домой вечером 12 октября, Коля и Фима сильно устали и, поужинав и помывшись, сразу легли спать. На следующий день, 13 октября (это была суббота) мальчики пошли в школу и размышляли о том, как по аналогии с олимпиадной задачей найти решение задачи о пароле к СОМВ. Фима предположил, что, как и в олимпиадной задаче, в задаче о пароле к СОМВ необходимо, начиная с нерекуррентного правила 4 (f(2x2) = x), построить на основе рекуррентных правил 5, 6 и 7 цепочку значений функции, приводящую к решению уравнения f(x) = x. Но решить задачу подбором мальчику не удалось. Фима смог лишь найти значение аргумента, при котором значение функции отличается от него только первой цифрой: по правилу 4 f(22222) = 222, поэтому по правилу 7 f(822222) = 222222, а также значение аргумента, при котором значение функции отличается от него перестановкой третьей и четвертой цифр: по правилу 4 f(28222) = 822, поэтому по правилу 7 f(828222) = 822822. Но больше Фима, ни Коля так и не смогли продвинуться ни на шаг к разгадке данной тайны. Поэтому после обеда мальчики опять поехали к Павлу Игнатьевичу. Благо, он был на кафедре, и притом был свободен и смог принять мальчиков.

Павел Игнатьевич подсказал Коле и Фиме следующий план решения задачи:

— Назовем базовым обычное (т. е. нерекуррентное) правило, на основе которого путем применения рекуррентных правил строится цепочка значений функции от различных аргументов. Какие правила можно использовать в качестве базовых?

Немного подумав, Коля ответил:

— Четвертое и восьмое.

— Правильно, — сказал Павел Игнатьевич. Можно ли найти решения уравнения f(x) = x, используя в качестве базового правило 8?

После долгих размышлений Фима смог найти ответ на данных вопрос:

— Поскольку правило 8 определяет значения функции f, равные нулю (и на основании него невозможно добиться равенства значения функции аргументу), а рекуррентные правила 5, 6 и 7 приписывают к аргументу функции слева цифры 4, 6 и 8, тогда как к результату функции может быть дописана слева цифра 2, цифры результата могут быть повернуты в обратном порядке или повторены один или несколько раз, но, во всяком случае, применение любой комбинации правил 5, 6, 7, использованных на базе правила 8 (один или несколько раз и в любом порядке), приведет к тому, что аргумент функции будет содержать (опять-таки один или несколько раз и в любом порядке) как минимум одну из трех цифр: 4, 6, 8 (а возможно, две или все три цифры), тогда как результат может состоять только из цифр 0 и 2 и не может содержать ни одной из цифр 4, 6 и 8. Стало быть, в данном случае значение функции не может быть равно аргументу, т. к. они содержат различные цифры.

— Итак, — продолжил Павел Игнатьевич, — базовым правилом, позволяющим найти решение задачи, может быть только правило 4. По аналогии с олимпиадной задачей имеем: f ((2x2))= x, где x — целое неотрицательное число, содержащее не более восьми цифр.

— А почему не более восьми? — спросил Коля.

— Потому что число (2x2) должно принадлежать области определения функции f, т. е. содержать не более десяти цифр. Удаляя начальную и конечную двойки, получаем, что на долю числа x причитается не более восьми цифр.

— Хорошо, Павел Игнатьевич, а как будем действовать дальше? — спросил Коля.

— Прежде всего необходимо определить, какое именно правило позволяет добиться равенства количества цифр аргумента и значения функции, — продолжил Павел Игнатьевич.

— Подумаем, — начал Фима. — По правилу 4, значение функции будет содержать на две цифры меньше, чем аргумент. Правило 5 прибавит четверку слева в аргумент, а двойку — в результат. В итоге и аргумент, и результат удлинятся на одну цифру, и соотношение количеств цифр не изменится. Правило 6 добавит одну цифру (а именно шестерку) в аргумент, тогда как результат "перевернется" (его цифры будут записаны в обратном порядке) и не изменит количество своих цифр. В итоге разность количеств цифр увеличится еще на одну единицу. И, наконец, правило 7 увеличит количество цифр аргумента на единицу (слева будет добавлена восьмерка), и удвоит количество цифр результата (они будут повторены дважды). При этом вполне можно добиться равенства цифр аргумента и результата.

— Итак, — заключил Павел Игнатьевич, — равенство количеств цифр аргумента и значения функции можно добиться только путем применения правила 7. Какие особенности при этом должны приобрести аргумент и результат?

— Аргумент будет начинаться с цифры 8, а результат будет записываться некоторой группой цифр, повторенной дважды, — догадался Фима.

— Если правило 7 будет применено последним, то цифра 8 действительно будет первой цифрой аргумента, — продолжил Павел Игнатьевич. — А если после правила 7 мы еще приме́ним правило 6?

— Тогда аргумент будет начинаться с цифр 68, а результат, "перевернувшись", опять будет записываться некоторой группой цифр, повторенной дважды (только теперь эта группа по сравнению с предыдущим случаем также перевернется), — ответит Коля.

— А если мы после этого приме́ним правило 5? — спросил Павел Игнатьевич.

— Тогда к аргументу слева будет приписана четверка, а к результату — двойка, — ответил Фима. — Но в данном случае аргумент и результат не могут стать равными друг другу, т. к. будут начинаться с различных цифр.

— Таким образом, для того, чтобы найти решения уравнения f(x) = x на базе правила 4 (т. е. на базе формулы f ((2x2))= x), необходимо один или несколько раз применить (в любом порядке) правила 5, 6 и 7, причем правило 7 должно быть применено как минимум один раз, и последним в данной цепочке должно быть либо правило 7, либо правило 6, — констатировал Павел Игнатьевич. — Поскольку и в том, и в другом случае значение функции является числом, записываемым некоторой группой цифр, повторенной дважды, то какой вид должен принять при этом аргумент функции? — спросил он.

Коля надолго задумался, а Фима быстро нашел ответ:

— Тот же самый вид числа, записываемого группой цифр, повторенной дважды. Ведь аргумент функции должен быть равен ее значению.

— Совершенно верно, — сказал Павел Игнатьевич. А какой вид имеет аргумент функции по базовому правилу?

— Вид (2x2) — ответил Коля.

— А как наиболее простым способом преобразовать аргумент (2x2) к виду числа, записываемого группой цифр, повторенной дважды? — спросил Павел Игнатьевич.

— Добавить слева букву x — догадался Коля. — Тогда аргумент примет требуемый вид: (x2x2).

— Поскольку мы применяем (один или несколько раз и в любом порядке) правила 5, 6 и 7, причем правило 7 должно быть применено как минимум один раз, и последним в данной цепочке должно быть либо правило 7, либо правило 6, то какой вид должен принять при этом аргумент функции? — спросил Павел Игнатьевич.

— К виду (2x2), определяемому по базовому правилу 4, слева будут добавлены (один или несколько раз и в любом порядке) цифры 4, 6 и 8, причем цифра 8 будет добавлена как минимум один раз, и первой цифрой аргумента станет либо цифра 8, либо цифра 6, — ответил Фима.

— Тогда какой вид должно иметь число x — спросил Павел Игнатьевич.

— Поскольку число x добавляется слева к числу (2x2), определяемому по базовому правилу 4, то оно может содержать только цифры 4, 6 и 8 (каждая из них — один или несколько раз и в любом порядке), причем цифру 8 число x должно содержать как минимум один раз, а первой цифрой числа x может быть либо цифра 8, либо цифра 6, — ответил Фима.

— А что произойдет со значением функции в результате применения рекуррентных правил? — спросил Павел Игнатьевич.

— Оно преобразуется из вида x в вид (x2x2), — ответил Коля.

— А как преобразовать значение функции из вида x в вид (x2x2), используя правила 5, 6 и 7? — спросил Павел Игнатьевич.

— Добавить двойку справа и повторить цифры, — ответил Коля.

— Повторить цифры мы можем по правилу 7, — сказал Павел Игнатьевич, — а вот добавить двойку мы можем по правилу 5, но, к сожалению, не справа, а слева.

— Ну тогда можно по правилу 6 развернуть число x (получится число (x→)), по правилу 5 добавить двойку слева (получится число (2x→)), вновь по правилу 6 развернуть число (получится число (x2)), и, наконец, по правилу 7 повторить цифры числа (получится число (x2x2)), — догадался Фима.

— А что произойдет при этом с аргументом функции? — спросил Павел Игнатьевич?

— К аргументу, имеющему вид (2x2), слева будут последовательно добавлены цифры 6, 4, 6 и 8, и он примет вид (86462x2), — ответил Фима. — Поскольку тот же аргумент имеет вид (x2x2), то x = 8646 и x2x2 = 8646286462. Итак, f(8646286462) = 8646286462. Мы нашли одно из решений задачи! — воскликнул мальчик. — Один из паролей — число 8646286462.

— Молодец! — ответил Павел Игнатьевич и поцеловал Фиму в лоб. — Осталось найти второе решение.

— Можно переставить местами два последних действия при преобразованиях значения функции, предложенных Фимой, — догадался Коля. — Тогда x = 6846 и x2x2 = 6846268462. Поэтому f(6846268462) = 6846268462. Второй пароль — число 6846268462.

— Браво! — сказал Павел Игнатьевич и пожал Коле руку.

— Поскольку значение первого пароля больше второго, то первый пароль позволяет путешествовать в будущее, а второй — в прошлое, — добавил Фима.

— Прекрасно! — сказал Павел Игнатьевич. — Осталось только проверить, действительно ли найденные пароли удовлетворяют условиям задачи?

— Проверим, — сказал Фима. — По правилу 4, f(286462) = 8646. Тогда по правилу 6, f(6286462) = 6468. Тогда по правилу 5, f(46286462) = 26468. Тогда по правилу 6, f(646286462) = 86462. Тогда по правилу 7, f(8646286462) = 8646286462, что и требовалось доказать.

— По правилу 4, — начал Коля, — f(268462) = 6846. Тогда по правилу 6, f(6268462) = 6486. Тогда по правилу 5, f(46268462) = 26486. Тогда по правилу 7, f(846268462) = 2648626486. Тогда по правилу 6, f(6846268462) = 6846268462, что и требовалось доказать.

— Итак, задача полностью решена, — заключил Павел Игнатьевич, взглянув на часы. — Но сейчас уже четыре часа. У вас остался только один час, иначе Фома Остапович навсегда заблокирует режим машины времени, и СОМВ можно будет пользоваться только как лифтом. Бегите скорее!

Поблагодарив Павла Игнатьевича и попрощавшись с ним, Коля и Фима стремглав побежали к университетскому лифту, спустились на первый этаж, выбежали на улицу, прибежали к станции метро "Университет", приехали на "Проспект Мира", поднялись на поверхность и прибежали к дому на Втором Волхонском, 8. Фима с помощью "таблетки" открыл замок домофона, и мальчики вошли в дом. Коля побежал было к будке на первом этаже, но Фима, взглянув на часы, которые показывали 16:50, сказал:

— Пока будем возиться с лифтом, опоздаем... Бежим по лестнице в подвал!

Мальчики побежали по лестнице в подвал, пересекли колонный зал и подошли к будке. Фима открыл ее медным ключом. Мальчики вошли в нее, и Фима запер будку изнутри. Коля нажал на красную круглую кнопочку, расположенную слева от кирпичной стены, служащей входной дверью кабины СОМВ, и последняя с музыкальным звуком открылась, отойдя вправо. Мальчики вошли в кабину и побежали к левой двери "Махагона". Фима открыл ее маленьким золотым ключиком, вошел внутрь и повернул тумблер (который по умолчанию автоматически перешел в режим лифта) в режим машины времени. Затем вышел из шкафа и запер его маленьким золотым ключиком. Мальчики побежали к столбику с пультом управления и встали в круг. В первой строке табло зелеными цифрами были указаны текущие дата и время: 13.10.1984, 16:57:00. На всё — про всё у Коли и Фимы осталось только три минуты...

Фима нажал на маленькую квадратную белую кнопку с цифрой 0. По рации раздались пять коротких отрывистых звуковых сигналов, на панели управления загорелся индикатор "Пуск", кнопки с цифрами от 1 до 9 перелились всеми цветами радуги, а дверь кабины СОМВ с музыкальным звуком закрылась. После этого Фима нажал на красную кнопку с цифрой 1, расположенную в нижней части пульта управления. В нижней части пульта загорелся индикатор "Исходная станция", а кнопки с цифрами от 1 до 9 вновь перелились всеми цветами радуги. С помощью белых кнопок с цифрами от 0 до 9 Фима набрал дату и время назначения: 13.10.2084, 17:00:00, а затем нажал на красную кнопку с цифрой 2. Загорелся индикатор "Конечная станция", кнопки с цифрами от 1 до 9 в третий раз перелились всеми цветами радуги, и Фома Остапович приказал:

— Встаньте в круг!

Убедившись в том, что они уже стоят в круге, мальчики хором ответили:

— Уже стоим!

Фома Остапович отдал им новый приказ:

— Возьмитесь за поручни!

Осмотревшись по сторонам и не увидев никаких поручней, Коля и Фима, взволнованные в результате пережитых приключений, опять начисто забыли о своём предшествующем опыте использования данного устройства и с удивлением спросили:

— Где?

Из боковых сторон столбика выскочили два металлических поручня, и мальчики крепко взялись за них своими руками. Фома Остапович приказал им:

— Закройте глаза!

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

— Дышите глубоко! — таков был следующий приказ Фомы Остаповича.

Мальчикам пришлось сделать серию глубоких вдохов. Но в это время они (по-видимому, от волнения) опять не смогли сдержать чувство любопытства. На этот раз Коля открыл правый, а Фима (о, Боже! — какая непозволительная дерзость!) — левый глаз. Мальчики посмотрели вперёд и не обнаружили никаких новых изменений в кабине СОМВ.

Но Фома Остапович сердито рявкнул на них:

— Сколько раз повторять, не подглядывайте! Ведь вы уже сто первый раз пользуетесь этой машиной!

— Простите нас, Фома Остапович! — виноватым тоном хором сказали мальчики. — Мы больше не будем!

— Ничего не поделаешь, придется повиноваться и немножко потерпеть — подумали при этом Коля и Фима и покорно закрыли глаза, опять пожав при этом плечами.

По рации раздался новый приказ Фомы Остаповича:

— Откройте глаза и введите пароль!

Помня, что мальчикам надо попасть в будущее, Фима ввел пароль: 8646286462 (он отобразился в третьей строке табло пульта управления синими цифрами) и нажал на красную кнопку с цифрой 2. В течение пяти секунд внутри столбика с пультом управления было слышно шуршание, после чего по рации раздался мощный голос Фомы Остаповича:

— Пароль обеспечивает доступ к путешествиям во времени из прошлого в будущее! Закройте глаза и не подглядывайте!

Перед тем, как закрыть глаза, мальчики увидели, что в верхней строке табло зелеными цифрами высветились текущие дата и время:

13.10.1984, 16:59:59

До вечной блокировки режима машины времени оставалась только одна секунда. Но Фима и Коля успели ее предотвратить!

Свет в кабине СОМВ погас, и она погрузилась в кромешную тьму. Только рядом с кругом, на котором стояли Фима и Коля, остался белый блик света, освещавший мальчиков, круг, столбик и его ближайшую окрестность. Фома Остапович запустил СОМВ по её главному назначению, и кабина вместе с пассажирами начала опускаться на триста метров под Землю.

Конец восьмой главы