Принцесса или тигр - Рэймонд Смаллиан

Можно подойти к решению этой задачи и по-другому. Из решения задачи 5 мы знаем, что существуют числа Z и W, при которых Z порождает NW, a W порождает MZ (а именно числа Z = 32N2M3 и W = 2M32N2M3). Тогда, согласно утверждению 1 из предыдущей главы, число MZ порождает M(NW), a число NW порождает N(MZ). Поэтому если мы обозначим MZ через X, a NW через У, то сразу получим, что число X порождает М(У), а число У порождает N(X). Таким образом, мы получаем то же самое решение: X = M32N2M3 и y = N2M32N2M3.

7. Здесь нам необходимо найти такое число X, которое порождало бы число М(AN2BX); согласно второму принципу Крейга, таким числом X является число M32AN2BM3. Возьмем N2BX в качестве У; тогда число X порождает М(АУ), а число У (которое есть N2BX), очевидно, порождает N(BX). Итак, общее решение задачи (или, по крайней мере, одно из возможных общих решений) имеет вид: X = M32AN2BM3, Y = N2BM32AN2BM3. Для конкретного частного случая положим М = 5, N = 4, А = 7 и В = 89.

8. Согласно второму принципу Крейга, существует некоторое число X, которое порождает М(2ВХ), а именно Х = М322ВМЗ. Положим теперь У=2ВХ. Тогда X порождает М(У), а У порождает ВХ. Для конкретного частного случая примем М = 3 и В = 78; при этом решение будет иметь вид: Х = 33227833, У = 27833227833.

9. а) Возьмем некоторое число X, которое порождает M(AN2X), и обозначим через У число N2X. (Мы можем взять X равным M32AN23, a y = N2M32AN23.) Тогда X порождает М(АУ), а У порождает N(X).

б) Теперь возьмем X, которое порождает М(А2ВХ), и обозначим через У число 2ВХ. (Итак, в этом случае решение имеет вид: Х = М32А2ВЗ, У = 2ВМ32А2ВЗ.)

в) Если число X порождает М(У), а У = 2Х, то мы сразу имеем решение задачи; поэтому положим Х = М322МЗ, У = 2М322МЗ.

г) Если X порождает М(АУ), а У = 2Х, то мы сразу получаем требуемое решение; поэтому положим Х = М32А2МЗ и У = 2М32А2МЗ.

10. Согласно второму принципу Крейга, существует некое число X, которое порождает M(N2P2X), a именно X = M32N2P2M3. Положим Y = N2P2X, тогда число X порождает М(У). Пусть теперь Z = P2X, тогда y = N2Z; при этом число У порождает N(Z), а число Z порождает Р(Х). Таким образом, в явном виде решение будет таким: X = M32N2P2M3,

Y = N2P2M32N2P2M3,

Z = P2M32N2P2M3.

Для частного случая это решение имеет вид: Х = 432523243, У = 5232432523243, Z = 32432523243.

Читатель сам может легко убедиться, что действительно X порождает обращение У, Y порождает повторение Z, a Z порождает ассоциат X.

Кстати говоря, для любых трех чисел А, В и С мы всегда можем найти такие числа U, V и W, при которых U порождает AV, V порождает BW, a W порождает CU. Для этого надо просто взять такое число U, которое порождало бы число А2В2СU (если же мы воспользуемся вторым принципом Крейга, то получим U = 32A2B2C3). Положим теперь V = 2B2CU и W = 2CU. Тогда число U будет порождать AV, число V будет порождать BW, а число W будет порождать CU. Наконец, если теперь принять А, В и С за операционные числа и положить X = AV, Y = BW и Z = CU, то мы получим, что число X порождает A(Y), число У порождает B(Z), а число Z порождает С(Х). Таким образом, мы нашли еще один способ решения данной задачи.

Остановимся, попробуем обобщить!

Два дня спустя полицейское начальство из Скотланд-Ярда внезапно и совершенно неожиданно для Крейга срочно откомандировало его в Норвегию для расследования, хотя и интересного, но нас не касающегося. Поэтому я воспользуюсь отсутствием Крейга, чтобы поделиться с вами кое-какими собственными соображениями по поводу числовых машин Мак-Каллоха. Те же читатели, которым не терпится узнать решение загадки сейфа из Монте-Карло, могут отложить чтение этой главы на потом.

Математики обожают обобщать! Сплошь и рядом случается так: некий математик по имени X доказывает новую теорему и публикует доказательство в научном журнале. Потом проходит полгода и появляется другой математик, Y, который вдруг заявляет: «Ну ладно, неплохую теоремку доказал этот X, однако я могу доказать гораздо более общий случай!» И тут же печатает статью под названием «Об одном обобщении георемы Х-а». Или же Y оказывается похитрее и поступает следующим образом: сначала он втайне обобщает теорему, доказанную Х-м, а потом исследует какой-нибудь частный случай своего обобщения. Этот частный случай по внешнему виду обычно настолько отличается от исходной теоремы, предложенной Х-м, что Y вполне может опубликовать полученный результат в качестве новой, оригинальной теоремы. Тут на сцене, естественно, появляется третий математик по имени Z: этого Z никак не оставляет чувство, что где-то теоремы Х-а и Y-a в чем-то важном очень сходны. Он начинает напряженно работать и… обнаруживает некий общий принцип. Z тут же публикует работу, в которой формулирует и доказывает этот новый общий принцип, а в заключение добавляет: «Теоремы, предложенные Х-м и Y-м, вполне могут рассматриваться как частные случаи нашего общего принципа, поскольку…»

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

Первое, что больше всего поразило меня при нашем обсуждении работы второй машины Мак-Каллоха, было то, что после введения правила 4 (правило повторения) мы уже больше не нуждаемся в правиле 2 (правило ассоциата) для того, чтобы получить принцип Крейга и законы Фергюссона! В самом деле, рассмотрим машину, в которой используются только правила 1 и 4. Для такой машины мы всегда можем найти некое число X, которое порождает само себя; можем также найти такое число, которое порождает повторение самого себя; задавая произвольное число А, мы можем найти такое число X, которое порождает АХ; наконец, мы можем найти число X, которое порождает повторение числа АХ или же повторение повторения АХ. Кроме того, используя машину Мак-Каллоха, из которой выведено правило 2, мы можем найти такое число X, которое порождает обращение самого себя, или число X, которое порождает повторение своего собственного обращения, или же число X, которое порождает обращение числа АХ, или, наконец, число X, которое порождает повторение обращения числа АХ. Далее, рассмотрим машину, в которой используются предложенные Мак-Каллохом правила 1, 2 и 4 (за исключением правила 3, то есть правила обращения). При такой машине у нас имеются два различных способа построения числа, которое порождает ассоциат самого себя, два способа построения числа, которое порождает свое собственное повторение; наконец, два способа построения числа, порождающего ассоциат своего повторения или повторение ассоциата самого себя.

Наконец, если у нас имеется произвольная машина, в которую заложены лишь правила 1 и 4, то принцип Крейга и законы Фергюссона продолжают выполняться и в этом случае. Таким образом, если бы мы вместо правила 2 воспользовались правилом 4, то для большинства задач, о которых шла речь в двух предыдущих главах, мы вполне могли бы получить альтернативные решения. (Понятно ли читателю, как все это можно сделать? Если нет, то можно обратиться к приведенным далее пояснениям.)

Я мог бы рассказать еще о многом, но лучше, пожалуй, будет сформулировать мои основные замечания в виде трех теорем.

Теорема 1. Закон Мак-Каллоха (который, как известно, гласит, что при любом А существует некое число X, которое порождает число АХ) оказывается справедливым не только для машин, подчиняющихся правилам 1 и 2, но и для машин, подчиняющихся правилам 1 и 4.

Теорема 2. Любая машина, которая подчиняется закону Мак-Каллоха, подчиняется также и двум принципам Крейга.

Теорема 3. Любая машина, которая подчиняется одновременно второму принципу Крейга и правилу 1, должна подчиняться также и всем законам Фергюссона.

Не сообразит ли читатель, как доказать все эти теоремы?

Решения

Рассмотрим сначала произвольную машину, которая подчиняется правилам 1 и 4. Как известно, при любом X число 52X порождает число XX; поэтому если выбрать в качестве X число 52, то мы получим, что число 5252 порождает число 5252. Итак, у нас есть число, которое порождает само себя. Кроме того, число 552552 порождает повторение самого себя. Далее, чтобы для любого А найти число X, которое порождает АХ, возьмем в качестве X число 52А 52 (в самом деле, оно порождает повторение числа А 52, которое есть число А52А52, то есть число АХ). Тем самым мы доказали теорему 1. (Если мы хотим найти число X, которое порождает повторение АХ, то в качестве X следует взять число 552А552.)

А теперь рассмотрим машину, которая подчиняется выведенным Мак-Каллохом правилам 1, 3 и 4. Числом, порождающим обращение самого себя, является, например, число 452452 (оно порождает обращение повторения числа 452, или, другими словами, обращение числа 452452). (Сравните его с предыдущим решением 43243.) Числом, которое порождает повторение обращения самого себя, является число 54525452. (Сравните его с прежним решением 5432543.)

Далее, рассмотрим машину, которая подчиняется правилам 1, 2 и 4. Мы знаем, что число 33233 порождает свой собственный ассоциат точно так же, как и число 352352. Что касается числа X, порождающего повторение самого себя, то у нас уже имеются два решения — это числа 35235 и 552552. Что же касается числа X, порождающего ассоциат повторения самого себя, то одним решением служит число 3532353; другим — число 35523552. Наконец, для числа, которое порождает повторение своего собственного ассоциата, также существуют два решения — это число 5332533 или число 53525352.