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

— Спокойно, спокойно, — не повышая голоса, но достаточно твердо прервал его Крейг. — Что же именно вы нашли?

— Еще не совсем нашел, — отвечал незнакомец уже не так возбужденно. — Но вот-вот найду и, когда найду, стану самым великим математиком всех времен и народов! Имена Галуа, Коши, Дирихле, Кантора…

— Ну хватит! — решительно сказал Крейг. — Может быть, вы все же расскажете мне, что именно вы хотите найти?

— Хочу найти? — воскликнул незнакомец с обидой. — Говорю вам, я почти нашел! Я почти придумал универсальную машину, которая сможет решать любые математические задачи! Имея такую машину, я буду знать все! Я смогу…

— А, мечта Лейбница! — сказал Крейг. — Лейбниц ведь тоже мечтал о такой машине. Боюсь только, что мечта эта неосуществима.

— Лейбниц! — презрительно усмехнулся незнакомец. — Лейбниц! Да он просто не знал, с чего начать! А у меня практически уже есть такая машина! Не хватает только нескольких мелочей… Но давайте я вам лучше поподробней расскажу о своих идеях.

— Я хочу построить некую машину M, — начал объяснения незнакомец (как выяснилось, звали его Уолтон), — с вполне определенными свойствами: сначала вы вводите в машину натуральное число х, потом натуральное число у — и тут машина начинает работать и выдает некоторое новое число, которое мы будем обозначать как М(х, у). Итак, М(х, у) — это результат, который мы имеем на выходе машины M в том случае, если на ее входе в качестве первого числа задать число х, а в качестве второго — число у.

— Пока все ясно, — сказал Крейг.

— Кроме того, — продолжал Уолтон, — под словом «число» я понимаю произвольное положительное целое число, поскольку только эти числа я и буду рассматривать в дальнейшем. Как вам, должно быть, известно, обычно говорят, что два натуральных числа имеют одинаковую четность, если они одновременно либо оба четны, либо оба нечетны; если же одно из них четно, а другое нечетно, то их называют числами с различной четностью.

Теперь для любого числа x мы будем обозначать через х* число вида М(х, х). Так вот, я хочу, чтобы моя машина обладала следующими тремя свойствами.

Свойство 1.Для любого числа a должно существовать некоторое число b, такое, что при любом x число М(х, b) будет иметь ту же самую четность, что и число М(х*,а).

Свойство 2.Для любого числа b должно существовать некоторое число а, такое, что при любом x число М(х, а) будет иметь другую четность по сравнению с числом М(х, b).

Свойство 3.Должно существовать число h, такое, что при любом x число М(х, h) будет иметь ту же самую четность, что и само х.

— Вот такими свойствами должна обладать моя машина, — заключил Уолтон.

Инспектор Крейг некоторое время молчал, размышляя.

— Ну и в чем же дело? — спросил он наконец.

— Увы! — отвечал Уолтон. — Сначала я построил машину со свойствами 1 и 2, потом — машину со свойствами 1 и 3, наконец, я сконструировал машину со свойствами 2 и 3. Все три машины прекрасно работают — вон там, в портфеле, у меня подробные схемы… Но когда я пытаюсь объединить все три свойства в одной машине, у меня ничего не получается.

— Что же именно у вас не получается? — поинтересовался Крейг.

— Да она вообще не работает! — воскликнул Уолтон с отчаянием. — Когда я ввожу в нее пару чисел (х, у), то вместо того, чтобы выдать мне результат, машина вдруг начинает странно гудеть, как будто в ней происходит нечто вроде короткого замыкания. Как вы думаете, отчего это может быть?

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

Через несколько дней инспектор Крейг написал Уолтону письмо. Начиналось оно так:

Дорогой мистер Уолтон!

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

Дальше Крейг объяснял, почему существование подобной машины логически невозможно. Можете ли вы сообразить, почему?

Полезно разбить решение этой задачи на три этапа:

1) показать, что для любой машины, обладающей свойством 1, при любом числе а должно существовать по крайней мере одно число х, такое, что число М(х, а) будет иметь ту же самую четность, что и само х;

2) показать, что для любой машины, обладающей свойствами 1 и 2, при любом числе b найдется некоторое число х, такое, что число М(х, b) будет иметь иную четность по сравнению с этим х;

3) ни одна машина не может объединить в себе свойства 1, 2 и 3.

а) Рассмотрим машину, обладающую свойством 1. Возьмем произвольное число а; тогда, согласно свойству 1, найдется число b, такое, что при любом x число М(х, b) будет иметь ту же самую четность, что и число М(х #, а). В частности, если положить x равным b, то число M(b, b) будет обладать той же самой четностью, что и число М(b #, а). Однако число М(b, b) — это просто b #, и, значит, число b # должно иметь ту же самую четность, что и число М(b #, а) . Таким образом, положив x равным числу b # , мы видим, что число М(х, а) имеет ту же самую четность, что и само число х.

б) Рассмотрим теперь некоторую машину, обладающую свойствами 1 и 2. Возьмем произвольное число b; тогда, согласно свойству 2, обязательно найдется число a, такое, что при любом x число М(х, а) будет иметь другую четность по сравнению с числом М(х, b). Но, согласно свойству 1, существует по крайней мере одно х, при котором число М(х, а) имеет ту же самую четность, что и само х, — мы только что доказали это в пункте а. Такое число x должно иметь другую четность по сравнению с числом М(х, a), поскольку оно одинаково по четности с числом М(х, а), а М(х, а) в свою очередь имеет иную четность по сравнению с числом М(х, b).