счет? И еще: существует ли определенное правило относительно того, какое же число выдает машина, если только ты решил, какое именно допустимое число в нее ввести?
— Дело тут не совсем так, — пояснил Мак-Каллох. — Решить ввести число еще недостаточно, надо действительно его ввести.
— Это понятно, — поправился Крейг. — Я лишь хотел спросить, известно ли заранее, какое число выдаст твоя машина, если в нее уже введено исходное число?
— Ну, конечно, — ответил Мак-Каллох. — Моя машина — это ведь не устройство для получения случайных чисел! Она действует по строго определенным законам. А теперь я объясню тебе правила ее работы, — продолжал Мак-Каллох. — Прежде всего под числом я понимаю произвольное целое положительное число; ведь моя нынешняя машина не умеет оперировать с отрицательными величинами и с дробями. Заданное число N при этом записывается обычным способом в виде некоторой последовательности цифр 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Вместе с тем моя машина может манипулировать только с числами, в которых нет нуля, например с числами вида 23 или 5492, но никак не с числами вида 502 или 3250607. Кроме того, если нам даны два числа N и М, то под NM мы понимаем вовсе не N, умноженное на М! Символом NM обозначается число, полученное следующим образом: вначале записываются цифры числа N, причем в том же порядке, в каком они следуют в N, а потом к ним последовательно приписываются цифры числа М. Так, например, если N равно 23, а М равно 728, то символом NM мы будем обозначать число 23728. Или же если N=4, а М=39, то под NM мы будем понимать число 439.
— Вот уж совершенно необычная операция с числами! — удивился Крейг.
— Ты прав, — согласился Мак-Каллох. — Но именно эту операцию машина понимает лучше всего. А теперь я объясню тебе некоторые правила ее работы. Кстати, мы говорим, что число X порождает число У, имея в виду, что X является допустимым числом и что если число X вводится в машину, то Y есть то число, которое оно выдает. Так вот, первое правило таково:
Правило 1. Для любого числа X число 2Х (то есть 2, за которым следует X, а не 2, умноженное на X!) является допустимым числом, причем число 2Х порождает число X. Например, число 253 порождает число 53, 27482 порождает 7482, 23985 порождает 3985 и т. д. Иными словами, если я ввожу в машину число 2Х, то она отбрасывает двойку в начале и выдает нам то, что остается, а именно — число X.
— Ну, это совсем просто, — заметил Крейг. — А како вы остальные правила?
— Машина использует только два правила, — продолжал Мак-Каллох. — Но сначала я хотел бы разъяснить еще кое-что. Так, для любого числа X исключительно важную роль играет число Х2Х; это число я называю ассоциатом числа X. Например, ассоциатом числа 7 является 727, а ассоциатом числа 594 будет 5942594. А теперь другое правило:
Правило 2. Для любых чисел X и У справедливо следующее утверждение: если число X порождает число У, то число ЗХ порождает ассоциат числа У.
Например, согласно правилу 1, число 27 порождает 7; следовательно, число 327 порождает ассоциат числа 7, то есть число 727. Точно так же 2586 порождает 586; поэтому 32586 порождает ассоциат числа 586, то есть 5862586.
В этот момент Мак-Каллох ввел в машину число 32586. После неимоверного скрежета и лязга машина, в конце концов, действительно выдала число 5862586.
— Вообще-то ее нужно чуточку смазать, — заметил Мак-Каллох. — А пока давай рассмотрим еще пару примеров, чтобы выяснить, насколько ты усвоил оба моих правила. Допустим, я ввожу в машину число 3327. Что она нам выдаст? Мы уже знаем, что число 327 порождает число 727, а число 3327 порождает ассоциат числа 727, то есть число 7272727. Какое же число порождается числом 33327? Так вот, если 3327 порождает 7272727 (как мы только что убедились), то 33327 должно порождать ассоциат числа 7272727, то есть 727272727272727. Еще один пример: 259 порождает 59, 3259 порождает 59259, 33259 порождает 59259259259, и, наконец, 333259 порождает 59259259259259259259259.
— Это понятно, — согласился Крейг. — Но пока единственные числа, которыми ты пользовался до сих пор и которые, по всей видимости, действительно что-то «порождают», — это числа, начинающиеся с цифры 2 или 3. А как быть с числами, которые начинаются, скажем, с четверки?
— Видишь ли, моя машина действительно воспринимает только числа, начинающиеся с цифры 2 или 3, но даже среди них не все числа оказываются допустимыми. Когда-нибудь я построю машину побольше, чтобы она могла воспринимать большее количество чисел.
— А какие числа, начинающиеся с цифры 2 или 3, оказываются неприемлемыми для твоей машины? — спросил Крейг.
— Ну, например, не является допустимым число 2, поскольку оно не попадает под действие ни правила 1, ни правила 2; однако любое многоразрядное число, начинающееся с цифры 2, является допустимым. Не будет, например, допустимым число, состоящее из одних только троек. Кроме того, не являются допустимыми числа вида 32, 332 или числа, задаваемые в виде произвольной цепочки троек, за которыми следует цифра 2. В то же время для любого числа X допустимыми будут числа 2Х, 32Х, 332Х и т. д. Короче говоря, допустимыми числами являются только числа вида 2Х, 32Х, 332Х, 3332Х, а также любая цепочка троек, за которыми следуют цифры 2Х. Далее, поскольку число 2Х порождает X, а число 32 X порождает ассоциат числа X, то число 332Х в свою очередь порождает ассоциат ассоциата числа X—число, которое логично называть двойным ассоциатом числа X, а соответственно число 3332Х будет давать нам ассоциат ассоциата числа X—это число будем называть тройным ассоциатом числа X — и т. д.
— Вот теперь я понял все до конца, — удовлетворенно заметил Крейг. — Правда, мне бы хотелось еще узнать, о каких это забавных свойствах твоей машины ты упоминал?
— Тут-то мы как раз и приходим к различного рода комбинаторным головоломкам, — пояснил Мак- Каллох. — О некоторых из них я и хочу тебе рассказать!
1. — Начнем с самого простого примера, — сказал Мак-Каллох. — Пусть имеется число N, которое порождает само себя; значит, когда ты вводишь его в машину, она выдает тебе то же самое число N. Не мог бы ты найти такое число?
2. — Прекрасно, — одобрил Мак-Каллох, когда Крейг показал ему свое решение. — А теперь еще об одной интересной особенности этой машины. Пусть имеется число N, которое порождает ассоциат самого себя; другими словами, если ты вводишь в машину число N, то она выдает тебе число N2N. Не сможешь ли ты отыскать это число?
Эта задача показалась Крейгу несколько труднее предыдущей, но в конце концов он справился и с ней. А вы сумеете ее решить?
3. — Превосходно, — сказал Мак-Каллох, взглянув на решение Крейга. — Единственно, что хотелось бы мне знать, — это каким путем ты шел, чтобы найти исходное число N: так сказать, методом «тыка» или же ты действовал по заранее намеченному плану? И кроме того, является ли найденное тобой N единственно возможным числом, порождающим ассоциат самого себя, или же существуют и другие такие числа?
Тогда Крейг рассказал о своем методе отыскания числа N в последней задаче, а также ответил на вопрос Мак-Каллоха о том, существуют ли другие возможные решения этой задачи. Скорее всего, ход суждений Крейга должен заинтересовать читателя; более того, он существенно облегчает нахождение решений нескольких задач этой главы.
4. — Кстати, по поводу моего последнего вопроса, — сказал Мак-Каллох. — Как ты решил первую задачу? Существуют ли еще какие-нибудь числа, которые порождают сами себя?
Ответ Крейга приведен в решениях.
5. — Далее, — продолжал Мак-Каллох, — имеется число N, которое порождает число 7N (то есть за семеркой следует N). Мог бы ты его найти?
6. — Рассмотрим еще один вопрос, — сказал Мак-Каллох. — Существует ли такое число N, чтобы
