— Погодите, — возразил Крейг. — А как могло случиться, что вы пользуетесь замком, который может навсегда испортиться из-за неверного набора шифра?
— Я очень возражал против установки этого замка, — ответил Мартинес. — Но совет директоров решил по-своему. Они заявили, будто бы механизм замка обладает настолько уникальными характеристиками, что они с лихвой компенсируют его недостаток, связанный с возможной порчей замка при наборе неправильной комбинации цифр.
— Вот уж действительно самая нелепая ситуация, с которой я когда-либо сталкивался, — заметил Крейг.
— Совершенно с вами согласен, инспектор, — воскликнул Мартинес. — Однако что же нам теперь делать?
— Честно говоря, пока мне в голову ничего не приходит, — отвечал Крейг. — По-видимому, я не смогу быть ничем вам полезен, поскольку не вижу здесь ничего такого, за что можно было бы зацепиться. Боюсь, вы пригласили меня напрасно.
— Как это, не за что зацепиться! — обрадовался Мартинес. — Если бы это было так, я бы никогда не осмелился пригласить вас.
— Вот как? — заинтересовался Крейг.
— Да-да, — начал свой рассказ Мартинес. — Не так давно в нашем банке работал очень интересный, хотя и несколько эксцентричный сотрудник. Он был по профессии математиком; особенно его занимали задачи, связанные с комбинаторикой. Страшно интересовался он и всякими секретными замками с шифрами — поверите ли, механизм нашего сейфа он мог изучать прямо часами. Так вот, он утверждал, будто бы замок нашего сейфа — самый необычный и самый хитроумный из всех, с которыми он когда-либо имел дело. Кроме того, он постоянно придумывал всякие головоломки, развлекая ими многих из нас. Так, однажды он написал статейку, где перечислялись некоторые свойства механизма замка; при этом он утверждал, что, зная эти свойства, мы сможем сами легко получить ту самую комбинацию цифр, с помощью которой открывается наш сейф. Он вручил нам свою рукопись в качестве забавной головоломки, чтобы было чем заняться на досуге, но задачка эта показалась многим моим коллегам слишком трудной, и вскоре все о ней забыли.
— И где же эта статья? — спросил Крейг. — Полагаю, ее не заперли в сейфе вместе с карточкой, на которой записан шифр?
— По счастью, нет, — сказал Мартинес, вытаскивая рукопись из ящика своего письменного стола. — Вот, я сохранил ее.
Инспектор Крейг внимательно просмотрел рукопись.
— Понятно, почему никто из вас не сумел решить эту головоломку. Судя по всему, она и в самом деле необычайно сложна! А не проще ли было бы в этом случае обратиться прямо к автору задачи, ведь он-то, конечно, вспомнит шифр или в крайнем случае сумеет восстановить его заново?
— Этот человек работал у нас под именем Мартина Фаркуса, но, мне кажется, это было вымышленное имя, — ответил Мартинес. — Позднее мы так и не смогли его разыскать.
— Да-а, — задумчиво произнес Крейг. — Тогда, я по лагаю, существует только один выход — попытаться разгадать головоломку, даже если на это может потребоваться несколько недель или месяцев.
— Тут есть еще одна сложность, о которой я вам не сообщил, — перебил Мартинес. — Мы непременно должны открыть сейф к первому июня нынешнего года. Дело в том, что в сейфе хранятся важные государственные документы, которые должны быть извлечены утром второго июня. Если до той поры нам не удастся раздобыть шифр, то придется взорвать сейф, несмотря на его стоимость. Правда, сами документы при этом не будут повреждены взрывом, поскольку они находятся в сверхпрочном внутреннем сейфе, расположенном достаточно далеко от входной двери наружного сейфа. Что же касается других хранящихся там ценностей — ну что ж, документы важнее всего! Правда, нам это влетит в копеечку, если все-таки придется прибегнуть к столь радикальному способу!
— Попробую что-нибудь придумать, — сказал Крейг, подымаясь. — Пока ничего не обещаю, но сделаю все, что смогу.
А теперь попробуем рассказать, что же было в рукописи Фаркуса. Прежде всего отметим, что во всех шифрах использовались не цифры, а буквы. Поэтому шифром, или комбинацией, мы будем называть произвольную последовательность букв, составленную из любых двадцати шести прописных букв английского алфавита. Такая последовательность может быть любой длины и включать в себя произвольное число букв, повторяющихся любое число раз. Например, комбинация BABXL представляет собой шифр, комбинация XEGGEXY также является шифром. Отдельная буква тоже может считаться комбинацией (комбинацией единичной длины). При этом одни комбинации букв (шифры) будут открывать замок, другие могут его полностью заблокировать, а третьи не будут оказывать на механизм замка никакого действия. Комбинации, не оказывающие на замок никакого действия, мы будем называть нейтральными. Далее мы будем использовать строчные буквы х и у для обозначения произвольных комбинаций, причем символ ху будет обозначать собой комбинацию х, за которой следует комбинация у. Так, если х представляет собой комбинацию GAQ, a y — комбинацию DZBF, то ху будет обозначать комбинацию GAQDZBF. Обращением, или обратной комбинацией, мы будем называть ту же комбинацию, но записанную в обратном порядке. Например, обращением комбинации BQFR является комбинация RFQB. Повторением хх комбинации х назовем комбинацию х, за которой вновь следует она сама; так, например, повторение комбинации BQFR есть BQFRBQFR.
Далее Фаркус (или как там его звали по-настоящему) вводит так называемые родственные по отношению к другим (или, быть может, по отношению к самим себе) комбинации, однако, к сожалению, нигде не оговаривает, что же скрывается под вводимым им понятием. Тем не менее он перечисляет несколько характерных свойств этого «родства» (что бы там под этим ни понималось), которые, по его мнению, позволяют достаточно искушенному человеку легко открыть замок! Он перечисляет следующие 5 основных свойств (которые, как он отмечает, выполняются для двух любых произвольных комбинаций х и у):
Свойство Q.Для любой комбинации х комбинация QxQ является родственной по отношению к х. (Например, комбинация QCFRQ является родственной комбинации CFR.)
Свойство L.Если комбинация х родственна у, то комбинация Lx родственна комбинации Qy. (Например, поскольку комбинация QCFRQ родственна по отношению к CFR, то, значит, комбинация LQCFRQ является родственной по отношению к комбинации QCFR.)
Свойство V, или свойство обращения.Если комбинация х родственна по отношению к комбинации у, тогда комбинация Vx родственна обращению комбинации у (обратной комбинации у). (Например, поскольку комбинация QCFRQ родственна по отношению к комбинации CFR, то, следовательно, комбинация VQCFRQ будет родственной по отношению к RFC.)
Свойство R, или свойство повторения.Если комбинация х родственна по отношению к комбинации у, то комбинация Rx будет родственна комбинации уу (повторению комбинации у). (Например, поскольку комбинация QCFRQ родственна по отношению к комбинации CFR, то комбинация RQCFRQ будет родственной по отношению к комбинации CFRCFR. Кроме того, как мы видели на примере, приведенном в свойстве V, комбинация VQCFRQ является родственной по отношению к RFC, и, стало быть, комбинация RVQCFRQ будет родственной комбинации RFCRFC.)
Свойство Sp.Пусть комбинация х родственна по отношению к комбинации у, тогда, если комбинация x блокирует замок, то комбинация у будет нейтральной; если же комбинация х является нейтральной, то комбинация у блокирует замок. (Например, мы убедились, что комбинация RVQCFRQ является родственной по отношению к комбинации RFCRFC. Следовательно, если комбинация RVQCFRQ будет блокировать замок, то комбинация RFCRFC не будет оказывать на механизм замка никакого действия, а если комбинация LVQCRFQ никакого действия на механизм замка не оказывает, то есть она является нейтральной, тогда комбинация RFCRFC блокирует замок.)
С помощью этих пяти условий действительно можно подобрать комбинацию, которая открывала бы замок. (Самая короткая комбинация, которая мне известна, имеет длину, равную 10, но, конечно, существуют и различные другие комбинации.)
Разумеется, вряд ли можно ожидать, что теперь читатель сразу же отыщет решение поставленной задачи; ведь с описанием работы этого механизма связана целая теория, к последовательному изложению которой мы перейдем в дальнейшем. Теория эта имеет отношение к некоторым очень интересным открытиям в области математики и теоретической логики.
По правде говоря, после встречи с Мартинесом Крейг несколько дней бился над головоломкой, однако безуспешно.
— Оставаться здесь дальше не имеет смысла, — решил Крейг. — У меня нет ни малейшего представления, сколько времени эта работа может у меня занять, полагаю, что вполне могу подумать над этим дома.
Итак, инспектор Крейг возвратился в Лондон. То, что загадка в конце концов была решена, произошло не столько благодаря усилиям Крейга и его друзей (с ними мы вскоре познакомимся), но и в силу удивительного стечения обстоятельств, которые вот-вот раскроются перед нами.
Удивительная числовая машина
Решения
— Я очень возражал против установки этого замка, — ответил Мартинес. — Но совет директоров решил по-своему. Они заявили, будто бы механизм замка обладает настолько уникальными характеристиками, что они с лихвой компенсируют его недостаток, связанный с возможной порчей замка при наборе неправильной комбинации цифр.
— Вот уж действительно самая нелепая ситуация, с которой я когда-либо сталкивался, — заметил Крейг.
— Совершенно с вами согласен, инспектор, — воскликнул Мартинес. — Однако что же нам теперь делать?
— Честно говоря, пока мне в голову ничего не приходит, — отвечал Крейг. — По-видимому, я не смогу быть ничем вам полезен, поскольку не вижу здесь ничего такого, за что можно было бы зацепиться. Боюсь, вы пригласили меня напрасно.
— Как это, не за что зацепиться! — обрадовался Мартинес. — Если бы это было так, я бы никогда не осмелился пригласить вас.
— Вот как? — заинтересовался Крейг.
— Да-да, — начал свой рассказ Мартинес. — Не так давно в нашем банке работал очень интересный, хотя и несколько эксцентричный сотрудник. Он был по профессии математиком; особенно его занимали задачи, связанные с комбинаторикой. Страшно интересовался он и всякими секретными замками с шифрами — поверите ли, механизм нашего сейфа он мог изучать прямо часами. Так вот, он утверждал, будто бы замок нашего сейфа — самый необычный и самый хитроумный из всех, с которыми он когда-либо имел дело. Кроме того, он постоянно придумывал всякие головоломки, развлекая ими многих из нас. Так, однажды он написал статейку, где перечислялись некоторые свойства механизма замка; при этом он утверждал, что, зная эти свойства, мы сможем сами легко получить ту самую комбинацию цифр, с помощью которой открывается наш сейф. Он вручил нам свою рукопись в качестве забавной головоломки, чтобы было чем заняться на досуге, но задачка эта показалась многим моим коллегам слишком трудной, и вскоре все о ней забыли.
— И где же эта статья? — спросил Крейг. — Полагаю, ее не заперли в сейфе вместе с карточкой, на которой записан шифр?
— По счастью, нет, — сказал Мартинес, вытаскивая рукопись из ящика своего письменного стола. — Вот, я сохранил ее.
Инспектор Крейг внимательно просмотрел рукопись.
— Понятно, почему никто из вас не сумел решить эту головоломку. Судя по всему, она и в самом деле необычайно сложна! А не проще ли было бы в этом случае обратиться прямо к автору задачи, ведь он-то, конечно, вспомнит шифр или в крайнем случае сумеет восстановить его заново?
— Этот человек работал у нас под именем Мартина Фаркуса, но, мне кажется, это было вымышленное имя, — ответил Мартинес. — Позднее мы так и не смогли его разыскать.
— Да-а, — задумчиво произнес Крейг. — Тогда, я по лагаю, существует только один выход — попытаться разгадать головоломку, даже если на это может потребоваться несколько недель или месяцев.
— Тут есть еще одна сложность, о которой я вам не сообщил, — перебил Мартинес. — Мы непременно должны открыть сейф к первому июня нынешнего года. Дело в том, что в сейфе хранятся важные государственные документы, которые должны быть извлечены утром второго июня. Если до той поры нам не удастся раздобыть шифр, то придется взорвать сейф, несмотря на его стоимость. Правда, сами документы при этом не будут повреждены взрывом, поскольку они находятся в сверхпрочном внутреннем сейфе, расположенном достаточно далеко от входной двери наружного сейфа. Что же касается других хранящихся там ценностей — ну что ж, документы важнее всего! Правда, нам это влетит в копеечку, если все-таки придется прибегнуть к столь радикальному способу!
— Попробую что-нибудь придумать, — сказал Крейг, подымаясь. — Пока ничего не обещаю, но сделаю все, что смогу.
А теперь попробуем рассказать, что же было в рукописи Фаркуса. Прежде всего отметим, что во всех шифрах использовались не цифры, а буквы. Поэтому шифром, или комбинацией, мы будем называть произвольную последовательность букв, составленную из любых двадцати шести прописных букв английского алфавита. Такая последовательность может быть любой длины и включать в себя произвольное число букв, повторяющихся любое число раз. Например, комбинация BABXL представляет собой шифр, комбинация XEGGEXY также является шифром. Отдельная буква тоже может считаться комбинацией (комбинацией единичной длины). При этом одни комбинации букв (шифры) будут открывать замок, другие могут его полностью заблокировать, а третьи не будут оказывать на механизм замка никакого действия. Комбинации, не оказывающие на замок никакого действия, мы будем называть нейтральными. Далее мы будем использовать строчные буквы х и у для обозначения произвольных комбинаций, причем символ ху будет обозначать собой комбинацию х, за которой следует комбинация у. Так, если х представляет собой комбинацию GAQ, a y — комбинацию DZBF, то ху будет обозначать комбинацию GAQDZBF. Обращением, или обратной комбинацией, мы будем называть ту же комбинацию, но записанную в обратном порядке. Например, обращением комбинации BQFR является комбинация RFQB. Повторением хх комбинации х назовем комбинацию х, за которой вновь следует она сама; так, например, повторение комбинации BQFR есть BQFRBQFR.
Далее Фаркус (или как там его звали по-настоящему) вводит так называемые родственные по отношению к другим (или, быть может, по отношению к самим себе) комбинации, однако, к сожалению, нигде не оговаривает, что же скрывается под вводимым им понятием. Тем не менее он перечисляет несколько характерных свойств этого «родства» (что бы там под этим ни понималось), которые, по его мнению, позволяют достаточно искушенному человеку легко открыть замок! Он перечисляет следующие 5 основных свойств (которые, как он отмечает, выполняются для двух любых произвольных комбинаций х и у):
Свойство Q.Для любой комбинации х комбинация QxQ является родственной по отношению к х. (Например, комбинация QCFRQ является родственной комбинации CFR.)
Свойство L.Если комбинация х родственна у, то комбинация Lx родственна комбинации Qy. (Например, поскольку комбинация QCFRQ родственна по отношению к CFR, то, значит, комбинация LQCFRQ является родственной по отношению к комбинации QCFR.)
Свойство V, или свойство обращения.Если комбинация х родственна по отношению к комбинации у, тогда комбинация Vx родственна обращению комбинации у (обратной комбинации у). (Например, поскольку комбинация QCFRQ родственна по отношению к комбинации CFR, то, следовательно, комбинация VQCFRQ будет родственной по отношению к RFC.)
Свойство R, или свойство повторения.Если комбинация х родственна по отношению к комбинации у, то комбинация Rx будет родственна комбинации уу (повторению комбинации у). (Например, поскольку комбинация QCFRQ родственна по отношению к комбинации CFR, то комбинация RQCFRQ будет родственной по отношению к комбинации CFRCFR. Кроме того, как мы видели на примере, приведенном в свойстве V, комбинация VQCFRQ является родственной по отношению к RFC, и, стало быть, комбинация RVQCFRQ будет родственной комбинации RFCRFC.)
Свойство Sp.Пусть комбинация х родственна по отношению к комбинации у, тогда, если комбинация x блокирует замок, то комбинация у будет нейтральной; если же комбинация х является нейтральной, то комбинация у блокирует замок. (Например, мы убедились, что комбинация RVQCFRQ является родственной по отношению к комбинации RFCRFC. Следовательно, если комбинация RVQCFRQ будет блокировать замок, то комбинация RFCRFC не будет оказывать на механизм замка никакого действия, а если комбинация LVQCRFQ никакого действия на механизм замка не оказывает, то есть она является нейтральной, тогда комбинация RFCRFC блокирует замок.)
С помощью этих пяти условий действительно можно подобрать комбинацию, которая открывала бы замок. (Самая короткая комбинация, которая мне известна, имеет длину, равную 10, но, конечно, существуют и различные другие комбинации.)
Разумеется, вряд ли можно ожидать, что теперь читатель сразу же отыщет решение поставленной задачи; ведь с описанием работы этого механизма связана целая теория, к последовательному изложению которой мы перейдем в дальнейшем. Теория эта имеет отношение к некоторым очень интересным открытиям в области математики и теоретической логики.
По правде говоря, после встречи с Мартинесом Крейг несколько дней бился над головоломкой, однако безуспешно.
— Оставаться здесь дальше не имеет смысла, — решил Крейг. — У меня нет ни малейшего представления, сколько времени эта работа может у меня занять, полагаю, что вполне могу подумать над этим дома.
Итак, инспектор Крейг возвратился в Лондон. То, что загадка в конце концов была решена, произошло не столько благодаря усилиям Крейга и его друзей (с ними мы вскоре познакомимся), но и в силу удивительного стечения обстоятельств, которые вот-вот раскроются перед нами.
Удивительная числовая машина
После того как инспектор Крейг возвратился в Лондон, он поначалу потратил массу времени, пытаясь разгадать загадку сейфа из Монте-Карло, но потом, так ничего и не добившись, счел за благо на некоторое время отложить злополучную задачу в сторону и немножко развеяться. Тут ему пришла в голову мысль навестить своего старого приятеля Нормана Мак-Каллоха, которого он не встречал уже несколько лет. Они подружились, еще будучи студентами Оксфордского университета, и Крейг всегда с большой теплотой вспоминал те дни и своего друга — отличного парня, правда, немного чудаковатого, который постоянно выдумывал всякого рода технические курьезы. И хотя наш рассказ относится ко времени, когда современные ЭВМ еще не были изобретены, Мак-Каллоху уже в ту пору удалось сконструировать нечто вроде механического счетно-решающего устройства, но, конечно, по нынешним меркам, весьма примитивного.
— В свое время я здорово развлекался с этой штукой, — объяснил приятелю Мак-Каллох. — Правда, никак не могу придумать, к чему бы полезному ее приспособить, но зато она обладает всякими занятными свойствами.
— Что же она умеет делать? — поинтересовался Крейг.
— А вот что, — бодро начал Мак-Каллох. — Ты вводишь в машину заданное число, а через некоторое время она сама выдает тебе число.
— То же самое число или какое-нибудь другое? — спросил Крейг.
— Это зависит от того, какое число в нее ввести.
— Понятно, — почесал в затылке Крейг.
— Кроме того, — продолжал Мак-Каллох, — моя машина воспринимает не все числа, а лишь некоторые из них. Поэтому те числа, которые ее устраивают, я буду называть допустимыми числами.
— Вся эта терминология звучит весьма логичной, — согласился Крейг, — но позволь мне узнать, какие числа для машины являются допустимыми, а какие нет. Имеется ли какое-нибудь правило на этот счет? И еще: существует ли определенное правило относительно того, какое же число выдает машина, если только ты решил, какое именно допустимое число в нее ввести?
— Дело тут не совсем так, — пояснил Мак-Каллох. — Решить ввести число еще недостаточно, надо действительно его ввести.
— Это понятно, — поправился Крейг. — Я лишь хотел спросить, известно ли заранее, какое число выдаст твоя машина, если в нее уже введено исходное число?
— Ну, конечно, — ответил Мак-Каллох. — Моя машина — это ведь не устройство для получения случайных чисел! Она действует по строго определенным законам. А теперь я объясню тебе правила ее работы, — продолжал Мак-Каллох. — Прежде всего под числом я понимаю произвольное целое положительное число; ведь моя нынешняя машина не умеет оперировать с отрицательными величинами и с дробями. Заданное число 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, чтобы число 3N порождало ассоциат самого числа N?
7. — А существует ли такое N, — спросил Мак-Каллох, — которое порождает ассоциат числа 3N?
8. — Пожалуй, самая интересная особенность моей машины заключается в том, — сказал Мак-Каллох, — что для любого числа А существует некое число У, которое порождает число AY. Как доказать это утверждение, и как по заданному числу А найти такое число У?
Примечание. Этот принцип, и в cамom деле очень простой, на практике оказывается еще более важным, нежели предполагал в тот момент Мак-Каллох! В этой книге мы столкнемся с ним еще не раз, и поэтому в дальнейшем будем называть его законом Мак-Каллоха.
9. — Далее, — продолжал Мак-Каллох, — всегда ли для сданного числа А существует некое число У, которое порождает ассоциат числа АУ? Существует ли, например, число, которое порождает ассоциат числа 56У, и если это так, то что это за число?
10. — Еще один интересный факт, — сказал Мак-Каллох, — заключается в том, что существует некоторое число N, которое порождает двойной ассоциат самого себя. Можешь ли ты найти это число?
11. — Кроме того, — сказал Мак-Каллох, — для любого заданного числа А существует число X, которое порождает двойной ассоциат числа АХ. Не мог бы ты сообразить, как найти такое число X, если число А нам задано? К примеру, как найти число X, которое порождает двойной ассоциат числа 78Х?
А вот еще несколько задач, с которыми Мак-Каллох познакомил в тот день Крейга. (За исключением последних, эти задачи не имеют особого теоретического значения, однако читателю, может быть, доставит удовольствие повозиться с ними)
12. Найти число N, такое, чтобы число 3N порождало число 3N.
13. Найти число N, такое, чтобы число 3N порождало число 2N.
14. Найти число N, такое, чтобы число 3N порождало число 32 N.
15. Существует ли такое число N, для которого числа NNN2 и 3N2 порождали бы одно и то же число?
16. Существует ли такое число N, ассоциат которого порождал бы число NN? Существует ли несколько таких чисел N?
17. Существует ли такое число N, для которого число NN порождало бы ассоциат этого N?
18. Найти число N, такое, чтобы ассоциат числа N порождал двойной ассоциат N.
19. Найти число N, которое порождает число N23.
20. Один отрицательный результат.
— Знаешь, — сказал Мак-Каллох, — я довольно долго пытался найти число N, которое порождает число N2, однако до сих пор все мои попытки не увенчались успехом. Интересно бы узнать, такое число на самом деле не существует или же у меня просто не хватает сообразительности, чтобы его отыскать?
Эта задача сразу завладела вниманием Крейга. Он тут же вытащил записную книжку и карандаш и погрузился в размышления. Спустя некоторое время он сказал:
— Не трать понапрасну силы, такое число просто не может существовать.
Как Крейг догадался об этом?
— В свое время я здорово развлекался с этой штукой, — объяснил приятелю Мак-Каллох. — Правда, никак не могу придумать, к чему бы полезному ее приспособить, но зато она обладает всякими занятными свойствами.
— Что же она умеет делать? — поинтересовался Крейг.
— А вот что, — бодро начал Мак-Каллох. — Ты вводишь в машину заданное число, а через некоторое время она сама выдает тебе число.
— То же самое число или какое-нибудь другое? — спросил Крейг.
— Это зависит от того, какое число в нее ввести.
— Понятно, — почесал в затылке Крейг.
— Кроме того, — продолжал Мак-Каллох, — моя машина воспринимает не все числа, а лишь некоторые из них. Поэтому те числа, которые ее устраивают, я буду называть допустимыми числами.
— Вся эта терминология звучит весьма логичной, — согласился Крейг, — но позволь мне узнать, какие числа для машины являются допустимыми, а какие нет. Имеется ли какое-нибудь правило на этот счет? И еще: существует ли определенное правило относительно того, какое же число выдает машина, если только ты решил, какое именно допустимое число в нее ввести?
— Дело тут не совсем так, — пояснил Мак-Каллох. — Решить ввести число еще недостаточно, надо действительно его ввести.
— Это понятно, — поправился Крейг. — Я лишь хотел спросить, известно ли заранее, какое число выдаст твоя машина, если в нее уже введено исходное число?
— Ну, конечно, — ответил Мак-Каллох. — Моя машина — это ведь не устройство для получения случайных чисел! Она действует по строго определенным законам. А теперь я объясню тебе правила ее работы, — продолжал Мак-Каллох. — Прежде всего под числом я понимаю произвольное целое положительное число; ведь моя нынешняя машина не умеет оперировать с отрицательными величинами и с дробями. Заданное число 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, чтобы число 3N порождало ассоциат самого числа N?
7. — А существует ли такое N, — спросил Мак-Каллох, — которое порождает ассоциат числа 3N?
8. — Пожалуй, самая интересная особенность моей машины заключается в том, — сказал Мак-Каллох, — что для любого числа А существует некое число У, которое порождает число AY. Как доказать это утверждение, и как по заданному числу А найти такое число У?
Примечание. Этот принцип, и в cамom деле очень простой, на практике оказывается еще более важным, нежели предполагал в тот момент Мак-Каллох! В этой книге мы столкнемся с ним еще не раз, и поэтому в дальнейшем будем называть его законом Мак-Каллоха.
9. — Далее, — продолжал Мак-Каллох, — всегда ли для сданного числа А существует некое число У, которое порождает ассоциат числа АУ? Существует ли, например, число, которое порождает ассоциат числа 56У, и если это так, то что это за число?
10. — Еще один интересный факт, — сказал Мак-Каллох, — заключается в том, что существует некоторое число N, которое порождает двойной ассоциат самого себя. Можешь ли ты найти это число?
11. — Кроме того, — сказал Мак-Каллох, — для любого заданного числа А существует число X, которое порождает двойной ассоциат числа АХ. Не мог бы ты сообразить, как найти такое число X, если число А нам задано? К примеру, как найти число X, которое порождает двойной ассоциат числа 78Х?
А вот еще несколько задач, с которыми Мак-Каллох познакомил в тот день Крейга. (За исключением последних, эти задачи не имеют особого теоретического значения, однако читателю, может быть, доставит удовольствие повозиться с ними)
12. Найти число N, такое, чтобы число 3N порождало число 3N.
13. Найти число N, такое, чтобы число 3N порождало число 2N.
14. Найти число N, такое, чтобы число 3N порождало число 32 N.
15. Существует ли такое число N, для которого числа NNN2 и 3N2 порождали бы одно и то же число?
16. Существует ли такое число N, ассоциат которого порождал бы число NN? Существует ли несколько таких чисел N?
17. Существует ли такое число N, для которого число NN порождало бы ассоциат этого N?
18. Найти число N, такое, чтобы ассоциат числа N порождал двойной ассоциат N.
19. Найти число N, которое порождает число N23.
20. Один отрицательный результат.
— Знаешь, — сказал Мак-Каллох, — я довольно долго пытался найти число N, которое порождает число N2, однако до сих пор все мои попытки не увенчались успехом. Интересно бы узнать, такое число на самом деле не существует или же у меня просто не хватает сообразительности, чтобы его отыскать?
Эта задача сразу завладела вниманием Крейга. Он тут же вытащил записную книжку и карандаш и погрузился в размышления. Спустя некоторое время он сказал:
— Не трать понапрасну силы, такое число просто не может существовать.
Как Крейг догадался об этом?
Решения
1. Таким числом является, например, число 323. В самом деле, поскольку число 23 порождает число 3 (согласно правилу 1), то, согласно правилу 2, число 323 должно порождать ассоциат числа 3, а это и есть 323 — как раз то же самое число!
Существуют ли другие такие числа?
По поводу ответа Крейга на этот вопрос смотри решение задачи 4.
2. Числом, которое нашел Крейг, было 33233. Действительно, любое число вида 332Х порождает двойной ассоциат X; так, число 33233 порождает двойной ассоциат числа 33 — то есть ассоциат ассоциата числа 33. Далее, ассоциат числа 33 есть исходное число 11233, и, следовательно, двойной ассоциат числа 33есть ассоциат числа 33233. Итак, число 33233 порождают ассоциат числа 33233, или свой собственный ассоциат.
Как же было найдено это число, и является ли полученное решение единственным? Крейг дает ответы на эти вопросы при решении следующей задачи.
3. Здесь рассказывается о том, как Крейг отыскал решение задачи 2, а также о том, как он сумел ответить на вопрос, существуют ли какие-либо другие решения этой задачи. Тут я предоставлю слово ему самому:
«Моя задача заключалась в том, чтобы найти число N, которое порождает число N2N. Ясно, что это число должно иметь вид 2X, 32Х, 332Х, 3332Х и т. д., причем мне нужно было отыскать X. Подошло бы в данном случае число вида 2X? Совершенно очевидно, что нет, поскольку число 2Х порождает число X, которое, понятно, является более коротким (содержит меньше цифр), чем ассоциат числа 2Х. Поэтому ни одно число вида 2Х никак не могло оказаться подходящим.
Что можно сказать по поводу числа вида 32Х? Оно также порождает ассоциат числа X, который, очевидно, содержит меньшее число цифр, нежели ассоциат числа 32Х.
Теперь попробуем число вида 332Х. Это число порождает двойной ассоциат числа X, который имеет вид Х2Х2Х2Х, тогда как нам необходимо получить ассоциат числа 332Х, то есть число, которое записывается в форме 332Х2332Х. Далее, может ли число Х2Х2Х2Х оказаться тем же самым числом, что и 332Х2332Х? Прежде всего, нужно сравнить относительную длину этих чисел. Так, если h—количество цифр в числе X, то число Х2Х2Х2Х должно иметь 4h+3 цифр (поскольку в нем четыре X и три двойки); в то же время число 332Х2332Х имеет 2h +7 цифр. Может ли 4h+3 равняться 2h+7? Да, но только в том случае, когда h=2. Итак, что касается длины, то число вида 332Х вполне может оказаться для нас подходящим, но лишь при условии, если количество цифр в X равняется двум.
Существуют ли еще какие-нибудь возможности? Посмотрим, например, что можно сказать по поводу числа вида 332Х. Такое число порождает тройной ассоциат числа X, который представляет собой число вида Х2Х2Х2Х2Х2Х2Х2Х, тогда как нам необходимо получить ассоциат числа 3332Х, который записывается как 3332X23332X. Могут ли эти числа оказаться одинаковыми? Вновь обозначая через h длину числа X, находим, что число Х2Х2Х2Х2Х2Х2Х2Х имеет 8h+7 цифр; в то же время число 3332Х23332Х имеет 2h+9 цифр. Равенство 8h+7 = 2h+9 может выполняться, только если h = 1/3, и, следовательно, в данном случае целочисленного значения не существует. Итак, числа вида 3332Х нам также не подходят.
Наконец, что можно сказать относительно числа вида 33332Х? С одной стороны, это число порождает четверной ассоциат числа X, который имеет длину 16/1 + 15; с другой стороны, сам ассоциат числа X имеет длину 2h+11. Ясно, что для любого целого положительного /I выражение 16h+15 больше, чем 2h+11, и, значит, число вида 33332Х порождает нечто слишком для нас большое.
Если мы теперь возьмем число, начинающееся не с 4, а с 5 троек, то несоответствие между длиной числа, которое оно вроде бы должно было порождать, и длиной числа, которое оно порождает на самом деле, окажется еще больше, а если мы возьмем число, начинающееся с 6 или более троек, то это несоответствие станет совсем большим. Таким образом, нам остается снова вернуться к числу 332 X как к единственно возможному решению задачи, причем X в этом случае должен быть числом, состоящим из 2 цифр. Итак, искомое число N должно иметь вид 332аb, где а и b — одиночные цифры, подлежащие определению.
Существуют ли другие такие числа?
По поводу ответа Крейга на этот вопрос смотри решение задачи 4.
2. Числом, которое нашел Крейг, было 33233. Действительно, любое число вида 332Х порождает двойной ассоциат X; так, число 33233 порождает двойной ассоциат числа 33 — то есть ассоциат ассоциата числа 33. Далее, ассоциат числа 33 есть исходное число 11233, и, следовательно, двойной ассоциат числа 33есть ассоциат числа 33233. Итак, число 33233 порождают ассоциат числа 33233, или свой собственный ассоциат.
Как же было найдено это число, и является ли полученное решение единственным? Крейг дает ответы на эти вопросы при решении следующей задачи.
3. Здесь рассказывается о том, как Крейг отыскал решение задачи 2, а также о том, как он сумел ответить на вопрос, существуют ли какие-либо другие решения этой задачи. Тут я предоставлю слово ему самому:
«Моя задача заключалась в том, чтобы найти число N, которое порождает число N2N. Ясно, что это число должно иметь вид 2X, 32Х, 332Х, 3332Х и т. д., причем мне нужно было отыскать X. Подошло бы в данном случае число вида 2X? Совершенно очевидно, что нет, поскольку число 2Х порождает число X, которое, понятно, является более коротким (содержит меньше цифр), чем ассоциат числа 2Х. Поэтому ни одно число вида 2Х никак не могло оказаться подходящим.
Что можно сказать по поводу числа вида 32Х? Оно также порождает ассоциат числа X, который, очевидно, содержит меньшее число цифр, нежели ассоциат числа 32Х.
Теперь попробуем число вида 332Х. Это число порождает двойной ассоциат числа X, который имеет вид Х2Х2Х2Х, тогда как нам необходимо получить ассоциат числа 332Х, то есть число, которое записывается в форме 332Х2332Х. Далее, может ли число Х2Х2Х2Х оказаться тем же самым числом, что и 332Х2332Х? Прежде всего, нужно сравнить относительную длину этих чисел. Так, если h—количество цифр в числе X, то число Х2Х2Х2Х должно иметь 4h+3 цифр (поскольку в нем четыре X и три двойки); в то же время число 332Х2332Х имеет 2h +7 цифр. Может ли 4h+3 равняться 2h+7? Да, но только в том случае, когда h=2. Итак, что касается длины, то число вида 332Х вполне может оказаться для нас подходящим, но лишь при условии, если количество цифр в X равняется двум.
Существуют ли еще какие-нибудь возможности? Посмотрим, например, что можно сказать по поводу числа вида 332Х. Такое число порождает тройной ассоциат числа X, который представляет собой число вида Х2Х2Х2Х2Х2Х2Х2Х, тогда как нам необходимо получить ассоциат числа 3332Х, который записывается как 3332X23332X. Могут ли эти числа оказаться одинаковыми? Вновь обозначая через h длину числа X, находим, что число Х2Х2Х2Х2Х2Х2Х2Х имеет 8h+7 цифр; в то же время число 3332Х23332Х имеет 2h+9 цифр. Равенство 8h+7 = 2h+9 может выполняться, только если h = 1/3, и, следовательно, в данном случае целочисленного значения не существует. Итак, числа вида 3332Х нам также не подходят.
Наконец, что можно сказать относительно числа вида 33332Х? С одной стороны, это число порождает четверной ассоциат числа X, который имеет длину 16/1 + 15; с другой стороны, сам ассоциат числа X имеет длину 2h+11. Ясно, что для любого целого положительного /I выражение 16h+15 больше, чем 2h+11, и, значит, число вида 33332Х порождает нечто слишком для нас большое.
Если мы теперь возьмем число, начинающееся не с 4, а с 5 троек, то несоответствие между длиной числа, которое оно вроде бы должно было порождать, и длиной числа, которое оно порождает на самом деле, окажется еще больше, а если мы возьмем число, начинающееся с 6 или более троек, то это несоответствие станет совсем большим. Таким образом, нам остается снова вернуться к числу 332 X как к единственно возможному решению задачи, причем X в этом случае должен быть числом, состоящим из 2 цифр. Итак, искомое число N должно иметь вид 332аb, где а и b — одиночные цифры, подлежащие определению.