Привет, не обсудить ли нам известный парадокс приговоренного? Согласно приговору, заключенного должны казнить в один из рабочих дней следующей недели, ровно в полдень, но неожиданно для него.
С одной стороны, вырисовывается противоречие: ведь в пятницу казнить нельзя, не будет неожиданно. Но тогда исключается и четверг, ведь это последний день, так как пятницу уже исключили. И так далее.
Но в среду неожиданно пришли и казнили.
И в этом полезно разобраться.
Итак, противоречие действительно есть: его хорошо видно, если сократить число дней до одного. Приговор "казнить в пятницу в полдень, но неожиданно" противоречив очевидным образом.
Противоречие означает, что палачи не могут выполнить все требования: казнить, казнить в пятницу в полдень и сделать это неожиданно. Возникает вопрос, что они будут делать. Вариантов у них не так много. Они могут нарушить требование, например, казнить в четверг, неожиданно. Или казнить в пятницу в полдень, и пусть бедняга орет, что он знал и правила нарушены. Но тогда задача теряет всю суть: если правило можно отменить, то считай что его и не было. Остается вариант "не казнить", который почему-то сразу приходит на ум. Но если палачи скажут: "э, налицо противоречие, казнить не будем, ещё из зарплаты вычтут за нарушение!", то визит их окажется сюрпризом и приговоренный вряд ли сможет скрыть свое удивление. Он, конечно, может и этот вариант просчитать, и мы приходим к сложному вопросу определения, что же значит "неожиданно" и как можно неожиданность доказать или опровергнуть. Скажем, если палачи придут, выслушают аргументы приговоренного, и выйдут пристыженные, то ничто не мешает им войти обратно и прикончить торжествующего узника.
Если дней хотя бы два (суббота или воскресенье), то всё ещё проще. С одной стороны, воскресенье исключается, но тогда отпадает и суббота - но если она отпадает, то по этой причине она годится. И узнику нечем крыть: палачи могут прийти за позором и завтра, и он не мог знать, что они выберут субботу. А раз не мог, то неожиданность налицо.
Это принцип самоприменимости, тот же, что в парадоксе лжеца. Утверждение "Это утверждение ложно" не может быть ни истинным, ни ложным. Если оно истинно, то ложно, а если ложно, то истинно.
Ближе к делу парадокс похитителя, который похитил нечто и готов вернуть, если хозяин угадает, собирается ли похититель вернуть вещь. Если хозяин скажет, что да, похититель волен поступить как захочет. Но если хозяин скажет, что нет, похититель нарушит свои же правила: вернув, он нарушит правило, так как ответ был неверен, а в этом случае он отдавать не собирался; а не вернув - так как ответ был верен, а в этом случае он обещал вернуть.
В парадоксе приговоренного всё тоньше, так как день годится именно потому, что не годится.
И здесь надо разобраться в глубинном смысле понятия "неожиданно". Допустим, палачи могут прийти, но узник отклонит приглашение на казнь, мотивируя свой отказ тем, что нарушены установленные приговором правила. В пятницу, последний день, он действительно может обоснованно отказаться (если палачи не могут не прийти - работа такая). Но в четверг - нет, ведь палачи могли и не приходить. Какая им разница, они могли прийти в пятницу и получить отказ. А пришли в четверг, и узник не мог этого знать заранее. Ситуация осложняется наличием среды и других дней: узник не может точно ждать гостей в среду, так как они могут прийти в четверг и настаивать на казни.
Легче понять смысл, отдалив границу: пусть казнь должна состояться в полдень в течение года. Тогда палачи могут прийти через месяц и потребовать согласия на казнь, и возражать будет трудно. Хотя что три дня, что 365 - это идентично.
А если граница в бесконечности, то есть казнить просто надо, в любой день - схема перестает работать вовсе.
Давайте уточним понятие "он ожидал". Если палачи просто приходят в любой день, и если казнить нельзя - уходят без последствий; то в пятницу узник сможет отболтаться, а вот в четверг - нет, ведь палачи спокойно могут прийти за отказом и в пятницу, им же ничего за это не будет.
Допустим, узник ведет прямую трансляцию. В пятницу, без пяти двенадцать, он может начать трансляцию, чтобы все видели, как он заставит с позором убраться палачей, которые не могут не прийти: приказ. И они придут, и уберутся. Но в четверг это уже сложнее: он будет вести трансляцию, а палачи не придут. А за ведение трансляции впустую его и казнят.
Или так: пусть у него есть граната, но только одна. Зная, что ровно в полдень его придут казнить, он может швырнуть ее в окошко двери, предотвратив свою казнь. В пятницу он так и поступит, но в четверг он не знает точно, придут или нет! Он может только рискнуть и кинуть (но эти или другие палачи придут в пятницу и прикончат) или рискнуть и не кинуть (и тогда если угадал, то спасся, а если нет, то нет).
Если палачи не слишком хотят попасть под гранату, а отобрать ее они не могут, то получается игровая ситуация. В случае всего двух дней она такая: палачи выбирают один из двух дней, и узник тоже. Если узник кинет гранату в первый день, его точно убьют во второй, а если подождет до второго, то спасется, если палачи решат прийти во второй. Последний вариант дает шанс, но палачам выгодно прийти в первый день.
Если же правила иные, и взорвавший палачей узник спасается, то ... это другая ситуация. Узник не знает точно, он угадывает. Но ладно, рассмотрим этот вариант. Узник кидает монетку, палачи тоже. Если выбор совпал, узник убегает, а если не совпал, узник погибает. Шансы равны. Чуть далее вернемся к этой игровой модели.
Теперь вернемся к доказательству. Пусть палачи не могут не выполнить приказ. То есть узник убеждает палачей, что казнить его нельзя, ведь он ждал их визита. Но палачей расстреляют за невыполнение приказа, чего они не желают. Узник убеждает их, что пятница не годится, не будет неожиданно, но поэтому не будет неожиданным и четверг, и любой другой день. Выполнить приказ невозможно, так что палачам надо просто идти сдаваться, или, как вариант, подавать апелляцию руководству, жалуясь на невыполнимый приказ. Палачи согласятся с рассуждением и пойдут к руководству. Руководство, рассмотрев жалобу, совершенно справедливо ее отклонит, предложив провести казнь в любой день. Даже в пятницу. Узник-то уверен, что убедил палачей не приходить. И именно это дает им основание прийти.
Наконец, можно подойти с позиций теории игр. Узнику надо доказать, что он ожидал визита, а палачам - что они пришли неожиданно. Палачи не могут не выполнить все условия, иначе очень много проиграют. Узник очень много проигрывает, если его казнят. Пусть дней всего два, это не влияет на суть: суббота или воскресенье.
Выбор палачей невелик: прийти в субботу, или прийти в воскресенье, и вообще не приходить. Вот с узником вопрос тоньше. Если он каждый день заявляет: "я жду вас сегодня!", то это, понятное дело, не годится. Он должен выбрать день и сказать: "сегодня придут". По ходу парадокса и говорится, что узник отметает все дни и приходит к выводу, что палачи вообще не придут. У него те же три варианта.
Можно считать, что выигрыш узника есть проигрыш палачей, и наоборот. Тогда игра описывается матрицей, в которой на диагонали стоят единички (выигрыш узника), а вне диагонали - "минус единички". Если узник придерживается стратегии "не придут", то палачам можно прийти в любой день, и это будет сюрпризом. Если он выберет какой-то день то палачи придут в другой. Узнику приходится играть смешанную стратегию, выбирая случайно одну из возможностей. Палачам - тоже.
Такую игру в смешанных стратегиях даже можно решить, найдя оптимальное распределение вероятностей, но здесь опять возникает терминологический вопрос. Узник должен точно знать, что сделают палачи, а не угадывать. Если он угадал, то он угадал, а не знал, а это не укладывается в семантику слова "неожиданно". Ведь палачи могут сказать "придем в субботу, с вероятностью 99%, ну или в воскресенье". И узник, зная это, все-таки не уверен полностью в субботе.
Поэтому так важно уточнять смысл слов. "Мы просто посмотрим на частицу" или "да возьмите синхронизированные часы с собой" или "взять всё, да поделить по справедливости" - это столь же бессмысленно, сколь и "Луна величиной с тарелку". Но это тема для отдельной беседы...
