пятница. ночь.

[avva]

Я бы и спать пошёл, да поработать надо ещё немного.

Is there anybody out there?

Давайте чего-нибудь интересное друг другу рассказывать. Или загадку какую. Или задачку. Если я что придумаю, в комментах напишу.

Comments

[kypexin.livejournal.com]

итак

одного человека приговорили к смертной казни и посадили в камеру. при этом ему сказали следующее -- ты будешь казнён в любой из дней следующей недели, но при этом ты узнаешь о том, что тебя казнят именно сегодня, _не раньше_ утра дня казни.

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

"допустим, меня казнят на следующей неделе в последний день недели, в воскресенье. но тогда, если я не узнаю о казни в субботу утром, то уже в субботу я буду знать о том, что меня казнят в воскресенье, то есть _за день_ до казни, а это противоречит поставленному условию (я должен узнать о казни только в воскресенье утром). поэтому в воскресенье меня не могут казнить, и для казни остаются только 6 дней следующей недели, а не 7 -- исключая воскресенье"

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

обрадованный, он сидел в камере и предавался размышлениям о том, что он останется жив. однако, в четверг утром в его камеру зашли охранники и объявили, что сегодня днём он будет казнён. и условие приговора было соблюдено -- ведь в четверг утром он был уверен, что сегодня его казнить не могут! однако же, его казнили в полном соответствии с условиями...

и вот вопрос -- кто рассуждал неправильно и почему?

[avva.livejournal.com]

У Мартина Гарднера в одной из книг была целая глава посвящена этому парадоксу.

На этом я умолкну и предоставлю возможность другим подумать на эту тему ;)

[kypexin.livejournal.com]

ну конечно я знал, что вы знали :)
просто это моя любимая задачка, которую я часто задаю :)))

но тем не менее жду решения от других, anyway :))))

нетривиально!

[(Anonymous)]

Насколько мне известно, не существует никакого *простого* объяснения этому парадоксу. Весьма исчерпывающий анализ проводится на 13 страницах в этой статье: http://www.univ-corse.fr/~franceschi/sep(gb).pdf -- но я не могу сказать, что приведенные там рассуждения полностью меня убеждают. А что пишет Мартин Гарднер? Расскажите, Авва, если знаете.
А то так получите еще 100 комментариев, утверждающих, что это, мол, "очевидно".

[irod-i-ada.livejournal.com]

очень жизнеутверждающая задачка!

[dvor.livejournal.com]

либо я тупая, либо это очевидно
уже в пятьницу остается два варианта - суббота или воскресенье
стало быть, он не знает, в какой день из этих двух его казнят
так что начиная со второго дня он рассуждает неправильно
я права?

[kypexin.livejournal.com]

воскресенье уже отпало сразу до начала недели, так что в пятницу остаётся только суббота...

[a-e-o.livejournal.com]

Воскресенье отпадает только в субботу. А человек рассуждает еще перед понедельником. То есть начальные условия для индукции не выдержаны.

[dvor.livejournal.com]

ага. не сказано же, что ровно через неделю

[a-e-o.livejournal.com]

Не только в этом дело. Дело в том, что индукция применяется по-другому. То есть если в день A его точно не казнят, то, предполагая, что его не казнят в день N>=A, нужно показать, что его не казнят и в день N+1. Тогда все будет правильно. А в данном случае логическая глупость.

[dvor.livejournal.com]

ну да, я примерно так сначала и объяснила

[avva.livejournal.com]

Да нет, почему же? Можно вполне индукцию и в обратном порядке применять, благо речь здесь идёт о конечном числе дней.

Априори нет ничего странного в док-ве по индукции сверху вниз того, что он не может быть казнён в любой день 1<=N<=7, путём док-ва того, что он не может быть казнён в N=7, и того, что если он не может быть казнён в любой день N>A, то не может быть казнён и в N=A.

[a-e-o.livejournal.com]

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

[avva.livejournal.com]

Откуда взялось это "в данный момент времени (любой день перед "следующей неделей")" ? Индукция это не предполагает.

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

[dodododo.livejournal.com]

хорошая задачка. как раз для бессонницы))

[a-e-o.livejournal.com]

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

[shinkovskaya.livejournal.com]

аж голова заболела! ...ничего я в том не поняла, кроме того, что так всё время: сначала мозги пудрят, а потом казнят именно в тот момент, когда того совсем не ожидаешь.

[valera.livejournal.com]

если в субботу утром ему не сообщают, что его казнят -сегодня-, то да, он может считать, что его казнят в воскресенье, но суббота все равно не является тем -сегодня-, в котором его казнят.

то-есть, если он узнает в субботу о своей казни в воскресенье, все правила соблюденны - сегодня он не будет казнен.

только, если я прав, то задачка семантическая, а не логическая.

кста, сорри за всевозможные ошибки в русском :)

[flaass.livejournal.com]

Рассуждения заключенного были бы верны, если б ему разрешалось кричать "я знаю, сегодня вы меня казните! так что не имеете права!" не один раз, а первым делом каждое утро.

[(Anonymous)]

Но если его не казнили, то он на самом деле ничего не знал. В этом и прикол заключается ИМХО. Его и в воскресенье могут казнить. Если к ночи с субботы на воскресенье его не казнили, значит его должны казнить в воскресенье. Зная это и зная правила, преступник будет думать, что его и в воскресенье не казнят. А придут и казнят. И он будет этому ужасно удивлен.

~Krem/

[avva.livejournal.com]

Да, совершенно верно.

непонятно

[(Anonymous)]

Авва, это непонятно. Примерно то же самое (несколько подробнее) написано в wikipedia, но тем не менее не убеждает.
Можно, например, рассмотреть усеченный вариант задачи, когда преступнику сообщают, что его казнят _завтра_ и что это будет неожиданно. Исходя из этого осужденный решит, что это невозможно, поэтому когда его казнят, это действительно будет для него неожиданно... Так? То есть преступник исходит из того, что оба сообщения истинны, и решает, что первое ложно. В результате оба оказываются истинны. Но ведь он может заключить, что ложно второе сообщение: его казнят, но это не будет неожиданно. И когда его казнят -- это и не будет неожиданно, то есть исходная конъюнкция окажется ложной...
Я, честно говоря, не могу теперь даже сформулировать, что именно мне не нравится, но что-то не нравится. Если Вам все кристально ясно, можете разложить по полочкам?
P.S. Я где-то выше по треду дал ссылку на интересную статью на эту тему. Если все так просто, то зачем тогда там делается анализ на десять страниц?..

Re: непонятно

[avva.livejournal.com]

Я не успел ещё просто выше ответить.

Во-первых, спасибо за статью, интересная. Я пока только бегло просмотрел, т.к. времени нет.

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

P.S. Может, Вы хотите завести свой дневник в LJ? Я пришлю Вам код для создания, если нужен.

Re: непонятно

[(Anonymous)]

Поломал себе голову еще пару дней, но тщетно. Wikipedia приводит (http://en2.wikipedia.org/wiki/Unexpected_hanging_paradox), кстати, еще более укороченный вариант парадокса, который вроде бы локализует причину парадоксальности. Посмотрите, если интересно, чтобы попусту не пересказывать.

Насчет дневника: Вы мне, между прочим, предлагали уже как-то раз, когда мы дискутировали насчет ударений в русском языке :) Ну что ж, на второй раз, пожалуй, соглашусь. Мой мейл kobak@yandex.ru; Вам же все равно придет этот постинг по почте? Тогда я не буду писать отдельное письмо.

статья интересная

[kobak.livejournal.com]

Возвращаясь к давнишнему: в дискуссии в ru_math на эту же тему (http://www.livejournal.com/community/ru_math/77548.html) возникла ссылка на ОЧЕНЬ интересную статью по теме: http://arxiv.org/abs/math.LO/9903160. Крайне рекомендую, если еще не видели.