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

— Это понятно, — согласился Крейг. — Но пока единственные числа, которыми ты пользовался до сих пор и которые, по всей видимости, действительно что-то «порождают», — это числа, начинающиеся с цифры 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 равняется двум.