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

Сижу за решеткой в темнице сырой…

Узник, приговоренный к высшей мере наказания, однажды в воскресенье был вызван к начальнику тюрьмы (честнейшему человеку, никогда не обманывающему даже самых злейших врагов общества). Начальник сказал: "Вас казнят на следующей неделе, но в какой именно день, я вам не скажу. Вы узнаете об этом только утром в день казни".

Через некоторое время узник обрел способность нормально размышлять. Он немедленно сделал вывод, что казнить в следующее воскресенье его не могут: ведь тогда еще в субботу вечером будет ясно, что для казни остался один-единственный возможный день. Это будет означать, что узнику стал известен день казни еще до наступления этого дня, а такого не может быть по определению - ведь начальник никогда не лжет!

"Иными словами, последний возможный день для моей казни, - думал узник, - это суббота. Но тогда если меня не казнят в пятницу утром, то к вечеру пятницы я тоже буду точно знать день, когда меня должны казнить. Однако начальник сказал, что о дне казни я узнаю лишь утром, а не накануне вечером, - значит, и в субботу меня не могут казнить тоже".

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

Обычно изложение этой истории - "парадокса узника" - на этом и заканчивается. Парадокс здесь в том, что всегда говорящий правду начальник формулирует предписание о казни, выполнить которое невозможно из-за его противоречивости. Или все-таки возможно?

В среду утром заключенному, уже уверенному в своей безнаказанности, сообщили, что сегодня его казнят. Это явилось для него полной неожиданностью - и значит, условие начальника оказалось выполненным. Получается, что невыполнимое предписание оказалось возможным исполнить именно из-за его якобы невыполнимости! Каково?

Обсуждение первое

Один из первых же вопросов, на которые приходится отвечать: можно ли считать, что начальник сам назначает день казни? Можно сказать, что да. А можно и сказать, что это делает за него компьютер. Так и сделаем: чтобы не обсуждать стратегии поведения начальника тюрьмы, будем считать, что день казни он узнает по датчику случайных чисел. Возможные значения датчика - от 1 (понедельник) до 7 (воскресенье). Кроме того, поскольку число дней в неделе не играет особой роли, то можно сразу обобщить парадокс на случай N возможных дней казни и исследовать его при различных N.

При N=1 парадокс очень прост. Начальник говорит буквально следующее: "Вас казнят завтра, но до завтрашнего утра вы ничего об этом не узнаете". Это утверждение противоречиво само по себе, поэтому никакой информации узник из него вынести не сможет. Противоречивые утверждения не могут быть ни истинными, ни ложными. Иначе говоря, из всей информации парадокса можно сделать только один вывод: начальник тюрьмы не всегда говорит правду.

Наиболее интересно рассмотреть случай N=2. Повторим рассуждение заключенного именно в этом случае: "Меня не могут казнить во вторник, так как иначе я узнал бы об этом к вечеру понедельника. Но тогда меня должны казнить в понедельник, и я знаю об этом уже сейчас. Это противоречит утверждению начальника о том, что я не должен узнать дату казни до ее наступления". Дальше заключенный решает, что начальник солгал ему. И только утром в тот из двух дней, на который укажет компьютер, оказывается, что начальник сказал правду…

В чем здесь противоречие и в чем ошибка - в рассуждениях узника или в исходном утверждении начальника тюрьмы?

Обсуждение второе

Практически все, кто сталкивается с парадоксом именно в такой форме, считают противоречивым условие, сформулированное тюремщиком. Однако на просьбу указать на это противоречие начинают повторять именно рассуждения узника! Но раз рассуждения узника приводят к парадоксу, то они не могут быть использованы для объяснения этого парадокса! Чем же все-таки объясняется получающееся противоречие? Узника не могут казнить, не нарушив предписания, - и все-таки казнят.

Я предлагаю читателям пока подумать над этим самостоятельно. А также - над разницей между этим вариантом парадокса и тем, когда начальник сам (без помощи компьютера или какого-то другого датчика случайных чисел) назначает день казни.

А теперь - решение. Точнее, одно из возможных решений.

Начальник утверждает, что известие о казни будет для осужденного неожиданным. В каком смысле надо понимать эту "неожиданность"? Очевидно, в том, что узник не сможет точно предсказать день своей казни. Но сколько раз узнику разрешается делать такое предсказание? Если мы проанализируем рассуждения узника, то увидим, что он делает многократные предсказания о дне казни и меняет их в том случае, если предыдущее предсказание оказалось ложным. Но ведь такой процесс предсказательства явно не предполагался начальником тюрьмы!

Если же понимать утверждение начальника так, как он его и формулировал - что узнику разрешается сделать предсказание только один раз (например, назвать дату своей казни до наступления понедельника), то у заключенного нет никакой возможности точно узнать эту дату заранее. Его могут казнить или в понедельник, или во вторник (или в любой другой день недели в случае N=7) - в полном соответствии с информацией, сообщенной начальником тюрьмы.

Парадокс создается именно из-за неполноты условия, а также из-за двойственности интерпретации понятия "ожидаемая дата казни".

Откажемся от компьютера

Ну, а теперь поехали по второму кругу. Представьте себе, что дату казни выбирает сам начальник тюрьмы. Тогда для N=2 рассуждения узника безупречны и, следовательно, условия задачи противоречивы. Так? А что получается для N=7 или N=1998? По-прежнему ли задача определения дня казни, поставленная начальником перед заключенным, лишена смысла? Или уже нет? И если нет, то при каком конкретном N происходит переход от первой ситуации (противоречивость и бессмысленность условия) ко второй (условие корректно, а рассуждения узника ошибочны)?

Предположим, что для N-1 задача еще противоречива, а для N - уже нет. Если бы начальник выбрал любой из дней от второго до N-го, то у него была бы всего N-1 возможность. Значит, в этом случае задача была бы противоречивой. А раз мы предположили, что это не так, то начальник должен выбрать для казни только первый день! И это уже известно узнику, что снова-таки делает задачу противоречивой…

Все ли верно в предыдущем абзаце? В чем состоит правильное объяснение парадокса в этом случае и есть ли здесь вообще парадокс?

Подумайте - это иногда бывает очень полезно.

Если вы имеете возможность читать статьи на Web, заходите ко мне на страничку, там лежат наиболее полные (и уже свободные от ошибок) версии моих статей. Хочу также поблагодарить всех читателей, заметивших ошибку в табличке 20x25 из статьи "Острова в океане". Эта ошибка исправлена в одном из последних выпусков "хвостов", а также в статье на моей homepage.