об одной хорошей загадке
Feb. 12th, 2008 07:55 pmТерри Тао (гениальный математик) написал в своем блоге запись о известной логической загадке (англ.). В комментариях у него ведутся долгие споры о том, верно ли кажущееся странным и противоречащим интуиции решение этой загадки, причем, что любопытно, на довольно низком уровне, т.е. там многие участники просто не понимают и продолжают нести чушь, хотя другие им пытаются объяснить. Учитывая авторитет автора блога, ситуация выходит несколько комическая, ну как если бы в блоге у Эйнштейна в комментариях какие-то неадекватные личности многословно критиковали принцип "все относительно" с моральной точки зрения.
Мне кажется, что я придумал довольно забавный способ посмотреть немного с другой стороны на решение загадки; по крайней мере мне самому этот аргумент раньше не встречался. Я описал это в комментарии у Тао, но, пожалуй, расскажу и здесь, пересказав вначале загадку и ее решение.
Загадка такая (есть много версий, это одна из них): один остров населен племенем, у членов которого бывают только голубоглазые или с глазами карего цвета. Всего на острове живет 1000 человек, из них 100 голубоглазых и 900 кареглазых. Все они как один придерживаются религии, которая строго запрещает им знать цвет своих глаз (в зеркала или воду они никогда не смотрят), или обсуждать цвет глаз кого-либо на острове. Каждый из них знает цвет глаз всех остальных, кроме себя, и если вдруг узнает цвет своих глаз, то он обязан, по своей религии, совершить публичное ритуальное самоубийство на площади на глазах у всего острова, в ближайший полдень.
В один прекрасный день на остров приплывает путешественник из далеких стран, и вскоре сдруживается со всеми жителями острова, которые полностью доверяют ему во всем.
Однажды вечером он созывает их всех, чтобы попрощаться и поблагодарить за гостеприимство. В конце своей речи он замечает, в частности, что для него - а у него голубые глаза - было приятной неожиданностью обнаружить в этой части света голубоглазого островитянина.
Вопрос: что происходит после этого заявления?
Загадка эта интересна тем, что можно придумать два аргумента, каждый из которых выглядит очень логичным, с противоположными выводами.
С одной стороны, путешественник не сообщил островитянам никакой новой информации. Он сказал им, что среди них есть хотя бы один голубоглазый житель; но каждый из них и так это знал, потому что видел вокруг себя кто 99, кто 100 голубоглазых жителей. Поскольку нет никакой новой информации, ничего особенного не случится.
С другой стороны, можно доказать, что ровно на сотый день все 100 голубоглазых жителей острова покончат жизнь самоубийством на площади (а тогда, естественно, на 101-й день за ними последуют все оставшиеся, кареглазые жители). Это легко доказать по индукции, и объяснить на примерах. Если бы, например, на острове был только один голубоглазый житель, то он сразу бы из заявления чужестранца узнал цвет своих глаз, и убил бы себя на первый день. Если бы было двое, каждый из них рассуждал был следующим образом: у меня либо голубые глаза, либо карие. Если карие, то голубые есть только у одного человека, и он должен себя убить на первый день. Так как на первый день никто себя не убил, то я знаю, что у меня голубые глаза, и убью себя на второй день.
И так далее. Если есть N жителей с голубыми глазами, каждый из них рассуждает: если бы у меня были карие глаза, то всего есть N-1 голубоглазых, и на N-1-й день они все должны убить себя. Поэтому он ждет N-1-го дня, видит, что этого не произошло, и на N-й день кончает жизнь самоубийством.
Какой из этих двух аргументов верный? Второй: правильное решение действительно состоит в том, что все голубоглазые убьют себя на 100-й день. Многим это решение кажется очевидно неверным или надуманным, и они отказываются в него поверить. На самом деле для того, чтобы действительно хорошо его понять, стоит как следует продумать его несколько раз, особенно для случая с 2 и 3 голубоглазыми жителями.
Как же объяснить то, что нет новой информации? На самом деле есть, но весьма тонкого плана: новая информация состоит в том, что *все* знают, что есть голубоглазый житель. В случае, когда есть только два голубоглазых, скажем А и Б, это легко понять. А знает, что есть хотя бы один голубоглазый житель, т.к. он видит Б, но он не знает, что Б это знает: может быть, у А карие глаза, и Б не видит ни одного голубоглазого. Заявление чужестранца позволяет дает А и Б новую информацию: теперь А знает, что Б знает, и вышеописанный аргумент срабатывает.
Но уже в случае троих голубоглазых, А, Б и В, это немного сложнее объяснить. Ведь А знает, что Б знает, что есть хотя бы один голубоглазый: Б, как и А, видит В. Где же новая информация? Когда я прочитал пару дней назад запись Тао, я понял, что не до конца это понимаю, и надо как следует продумать (хоть я и знал эту загадку раньше).
Предположим, например, что чужестранец ничего не говорил; мог бы А все равно рассуждать, как в решении? А говорит себе: Б и В знают, что есть хотя бы один голубоглазый. Предположим, что у меня карие глаза; тогда Б видит одного только В, и говорит себе: если у меня карие глаза, то В должен на следующий день убить себя... стоп, почему? В этом гипотетическом мире Б не знает, что В видит хотя бы одного голубоглазого! А знает это, но сейчас А ставит себя на место Б в гипотетическом мире с кареглазым А, а у Б в таком мире этой информации нет. Аргумент рассыпается. А вот если чужестранец сказал, что сказал - тогда этот гипотетический Б знает, что В знает, и поэтому может сказать: либо В убьет себя завтра, либо у меня голубые глаза.
Т.е. есть просто информация (я знаю, что есть хотя бы один голубоглазый); есть мета-информация (я знаю, что Б знает, что есть хотя бы один голубоглазый, даже если у меня карие глаза); есть мета-мета-информация (я знаю, что Б знает, что В знает, что есть хотя бы один голубоглазый, даже если у А и Б карие глаза...) и так далее и так далее. И утверждение чужестранца одновременно проясняет *все* эти варианты, и просто, и мета, и мета-мета итд. В этом "общем знании" состоит новизна его информации.
Это о загадке. Теперь немного о моих мыслях на эту тему.
Мне пришло в голову, что я ни разу не видел, в контексте этой загадки, обсуждения возможного самопожертвования, с целью спасти других. Пусть я один из жителей, то ли голубоглазый, то ли кареглазый. Сразу после заявления иностранца я рассуждаю примерно следующим образом:
Моя версия решения загадки, таким образом, состоит в следующем: сразу после заявления чужестранца один из жителей острова, известный одновременно своим умом и жестокостью, немедленно набросится на какого-то голубоглазого жителя (может, есть какой-то из них, кого все ненавидят?), и убьет его на месте. После чего все оставшиеся жители будут жить долго и счастливо. Разве что чужестранцу отрежут язык, скажем, чтобы не болтал почем зря. Я бы их за это не осудил.
Мне кажется, что я придумал довольно забавный способ посмотреть немного с другой стороны на решение загадки; по крайней мере мне самому этот аргумент раньше не встречался. Я описал это в комментарии у Тао, но, пожалуй, расскажу и здесь, пересказав вначале загадку и ее решение.
Загадка такая (есть много версий, это одна из них): один остров населен племенем, у членов которого бывают только голубоглазые или с глазами карего цвета. Всего на острове живет 1000 человек, из них 100 голубоглазых и 900 кареглазых. Все они как один придерживаются религии, которая строго запрещает им знать цвет своих глаз (в зеркала или воду они никогда не смотрят), или обсуждать цвет глаз кого-либо на острове. Каждый из них знает цвет глаз всех остальных, кроме себя, и если вдруг узнает цвет своих глаз, то он обязан, по своей религии, совершить публичное ритуальное самоубийство на площади на глазах у всего острова, в ближайший полдень.
В один прекрасный день на остров приплывает путешественник из далеких стран, и вскоре сдруживается со всеми жителями острова, которые полностью доверяют ему во всем.
Однажды вечером он созывает их всех, чтобы попрощаться и поблагодарить за гостеприимство. В конце своей речи он замечает, в частности, что для него - а у него голубые глаза - было приятной неожиданностью обнаружить в этой части света голубоглазого островитянина.
Вопрос: что происходит после этого заявления?
Загадка эта интересна тем, что можно придумать два аргумента, каждый из которых выглядит очень логичным, с противоположными выводами.
С одной стороны, путешественник не сообщил островитянам никакой новой информации. Он сказал им, что среди них есть хотя бы один голубоглазый житель; но каждый из них и так это знал, потому что видел вокруг себя кто 99, кто 100 голубоглазых жителей. Поскольку нет никакой новой информации, ничего особенного не случится.
С другой стороны, можно доказать, что ровно на сотый день все 100 голубоглазых жителей острова покончат жизнь самоубийством на площади (а тогда, естественно, на 101-й день за ними последуют все оставшиеся, кареглазые жители). Это легко доказать по индукции, и объяснить на примерах. Если бы, например, на острове был только один голубоглазый житель, то он сразу бы из заявления чужестранца узнал цвет своих глаз, и убил бы себя на первый день. Если бы было двое, каждый из них рассуждал был следующим образом: у меня либо голубые глаза, либо карие. Если карие, то голубые есть только у одного человека, и он должен себя убить на первый день. Так как на первый день никто себя не убил, то я знаю, что у меня голубые глаза, и убью себя на второй день.
И так далее. Если есть N жителей с голубыми глазами, каждый из них рассуждает: если бы у меня были карие глаза, то всего есть N-1 голубоглазых, и на N-1-й день они все должны убить себя. Поэтому он ждет N-1-го дня, видит, что этого не произошло, и на N-й день кончает жизнь самоубийством.
Какой из этих двух аргументов верный? Второй: правильное решение действительно состоит в том, что все голубоглазые убьют себя на 100-й день. Многим это решение кажется очевидно неверным или надуманным, и они отказываются в него поверить. На самом деле для того, чтобы действительно хорошо его понять, стоит как следует продумать его несколько раз, особенно для случая с 2 и 3 голубоглазыми жителями.
Как же объяснить то, что нет новой информации? На самом деле есть, но весьма тонкого плана: новая информация состоит в том, что *все* знают, что есть голубоглазый житель. В случае, когда есть только два голубоглазых, скажем А и Б, это легко понять. А знает, что есть хотя бы один голубоглазый житель, т.к. он видит Б, но он не знает, что Б это знает: может быть, у А карие глаза, и Б не видит ни одного голубоглазого. Заявление чужестранца позволяет дает А и Б новую информацию: теперь А знает, что Б знает, и вышеописанный аргумент срабатывает.
Но уже в случае троих голубоглазых, А, Б и В, это немного сложнее объяснить. Ведь А знает, что Б знает, что есть хотя бы один голубоглазый: Б, как и А, видит В. Где же новая информация? Когда я прочитал пару дней назад запись Тао, я понял, что не до конца это понимаю, и надо как следует продумать (хоть я и знал эту загадку раньше).
Предположим, например, что чужестранец ничего не говорил; мог бы А все равно рассуждать, как в решении? А говорит себе: Б и В знают, что есть хотя бы один голубоглазый. Предположим, что у меня карие глаза; тогда Б видит одного только В, и говорит себе: если у меня карие глаза, то В должен на следующий день убить себя... стоп, почему? В этом гипотетическом мире Б не знает, что В видит хотя бы одного голубоглазого! А знает это, но сейчас А ставит себя на место Б в гипотетическом мире с кареглазым А, а у Б в таком мире этой информации нет. Аргумент рассыпается. А вот если чужестранец сказал, что сказал - тогда этот гипотетический Б знает, что В знает, и поэтому может сказать: либо В убьет себя завтра, либо у меня голубые глаза.
Т.е. есть просто информация (я знаю, что есть хотя бы один голубоглазый); есть мета-информация (я знаю, что Б знает, что есть хотя бы один голубоглазый, даже если у меня карие глаза); есть мета-мета-информация (я знаю, что Б знает, что В знает, что есть хотя бы один голубоглазый, даже если у А и Б карие глаза...) и так далее и так далее. И утверждение чужестранца одновременно проясняет *все* эти варианты, и просто, и мета, и мета-мета итд. В этом "общем знании" состоит новизна его информации.
Это о загадке. Теперь немного о моих мыслях на эту тему.
Мне пришло в голову, что я ни разу не видел, в контексте этой загадки, обсуждения возможного самопожертвования, с целью спасти других. Пусть я один из жителей, то ли голубоглазый, то ли кареглазый. Сразу после заявления иностранца я рассуждаю примерно следующим образом:
Мда. Кажется, нам всем конец. На этом острове есть то ли 99, то ли 100 голубоглазых, и то ли на 99-й, то ли на 100-й день они все убьют себя (см. выше), а на следующий день - все остальные. Можно ли хоть как-то этого избежать?
Гм, а что если я убью себя раньше срока, точно по ритуалу, например на 99-й день? Я еще не буду знать цвет своих глаз, но условия не запрещают мне покончить жизнь самоубийством в любое другое время. Может, я смогу убедить других, что я знал цвет своих глаз, и запутать их, и тогда они спасутся? Если я кареглазый, то мое самоубийство на 99-й день ничего не изменит. Но если я голубоглазый, то все другие голубоглазые будут думать, что я убил себя на 99-й день, потому что видел только 99 голубоглазых, а после моей смерти осталось тогда только 98; но каждый из них и видит только 98 среди живых, и поэтому будет ошибочно думать, что у него карие глаза, а не голубые. Хотя... тогда они себя все равно убьют, но уже из-за этой уверенности. Ничего я не добился.
Хотя... они же все такие же умные, как я, и понимают, что мое самоубийство необязательно было "настоящим". Каждый из них думает так: если это самоубийство было настоящее, то у меня карие глаза, а если самопожертвование, то голубые; но точно я не знаю. Ура, они все выживут! Только вот что насчет кареглазых? Увы, это их не спасет. Каждый из них скажет себе: если бы у меня были голубые глаза, то это самопожертвование имело бы смысл на 100-м дне, а оно произошло на 99-м, значит, у меня карие глаза. Таким образом, на сотый день убивают себя все кареглазые, а на 101-й - оставшиеся голубоглазые. Ничего не вышло.
Ну и ладно, хрен с ним тогда, с этим ритуальным обманом. Надо разрубить Гордиев узел в его основе: лишить информацию, сообщенную чужестранцем, ее важности. Если до завтра, до первого дня, какой-либо голубоглазый житель острова умрет, то все остальные не смогут построить логическую цепочку, которая привела бы их к смерти на 100-й день, потому что мертвый житель не сможет участвовать в гипотетических рассуждениях! Например, я мог бы сейчас убить себя, пока толпа еще не разошлась после заявления чужестранца. Но если я кареглазый, это ничего не даст. Разве что другие жители сразу поймут, зачем я это сделал, и будут продолжать убивать себя по одному, пока не умрет какой-то голубоглазый. Но это значит, что мы пожертвуем примерно 9 жизнями зря, согласно пропорции. Нет уж, надо придумать что-то получше. Ага, знаю...
Моя версия решения загадки, таким образом, состоит в следующем: сразу после заявления чужестранца один из жителей острова, известный одновременно своим умом и жестокостью, немедленно набросится на какого-то голубоглазого жителя (может, есть какой-то из них, кого все ненавидят?), и убьет его на месте. После чего все оставшиеся жители будут жить долго и счастливо. Разве что чужестранцу отрежут язык, скажем, чтобы не болтал почем зря. Я бы их за это не осудил.
no subject
Date: 2008-02-13 05:24 pm (UTC)no subject
Date: 2008-02-13 06:37 pm (UTC)Я продолжаю утверждать, что знание о том, что голубоглазые есть уже присутствует в популяции. Однако для полного определения цвета собственных глаз этого знания недостаточно - нужно ещё и _событие_ - такое как факт отсутствия самоубийства других через фиксированное время после фиксириванного момента времени. До капитана Кука этого фиксированного момента в жизни туземцев не было.
no subject
Date: 2008-02-13 07:12 pm (UTC)no subject
Date: 2008-02-13 07:25 pm (UTC)Ведь даже заключение о том, что все другие должны убицца на такой-то день после выступления Колумба делается без предположения о цвете собственных глаз. Только когда это самоубийство _не происходит_, тогда с вероятностью 100% делается вывод об этом самом собственном цвете.
no subject
Date: 2008-02-13 07:41 pm (UTC)Эта цепочка вполне может выстраиваться и после заявления. Услышав слова о наличии синеглазого островитянина, я окидываю взором товарищей и, увидев, энное число синих глаз, как раз и говорю себе: вокруг меня три пары синих глаз. Я предполагаю, что каждый из них сочтет себя не синеглазым, и будет думать, что остальные синеглазые видят только две пары синих глаз и думают, что обладатели этих двух пар синих глаз будут думать, что на острове только один синеглазый и что если их предположение насчет собственной кареглазости верно, то этот один убьет себя в полдень, а если оно неверно, то им придётся убить себя вместе с ним, если верно предположение третьего синеглазого насчет свой кареглазости, а если оно неверно, то ему придётся убить себя вместе с ними на третий день, если верно моё предположение насчёт моей кареглазости, а если оно неверно, то мне придётся убить себя вместе с ними на четвёртый день, положив конец цепочке самоубийств.
no subject
Date: 2008-02-13 07:44 pm (UTC)Так об этом и речь. Как сказал другой товарищ в нескольких местах в этих тредах - путешественник не принёс никакой новой информации, он просто положил точку отсчёта синхронизованной цепочки логических умозаключений.
no subject
Date: 2008-02-13 07:51 pm (UTC)no subject
Date: 2008-02-13 07:57 pm (UTC)no subject
Date: 2008-02-13 08:10 pm (UTC)no subject
Date: 2008-02-13 08:23 pm (UTC)no subject
Date: 2008-02-13 08:40 pm (UTC)no subject
Date: 2008-02-13 10:32 pm (UTC)http://avva.livejournal.com/1873907.html?thread=48286707#t48286707
Мне кажется, доходчивей чем там, не объяснить.
no subject
Date: 2008-02-13 08:24 pm (UTC)no subject
Date: 2008-02-13 06:57 pm (UTC)Фактически этот третий туземец моего предположения (а ведь это все мои вложенные картины мира) не имеет ничего общего с реальным третим туземцем - потому как мои предположения о его мыслях находятся в противоречии с тем, что он видит. Значит, уже на этом этапе мне надо оборвать цепочку и решить, что одно из предположений было ошибочно, но не знаю какое - то, что у меня карие глаза или предположение второго о том, что у него карие глаза. То есть у меня по прежнему нет никакой новой информации и я не получил накаких "условно-практических" выводов (типа "если А, то завтра в полдень столько-то человек самоубъется"). В результате все туземцы остались живы.
no subject
Date: 2008-02-13 07:05 pm (UTC)http://avva.livejournal.com/1873907.html?thread=48285171#t48285171
no subject
Date: 2008-02-13 07:44 pm (UTC)Нас четверо, я вижу у троих голубые глаза. Я исключаю себя из числа голубоглазых, пока не доказано обратное. Я понимаю, что все трое голубоглазых также исключили себя из числа голубоглазых. По моим предположениям, каждый из оставшихся троих видит двух голубоглазых - себя-то я исключил. Это противоречит картине, которую вижу я, но я знаю, что для них подобная картина вероятна - при условии, что я кареглаз. До сих пор всё правильно? Далее. Остались трое голубоглазых, каждый из них считает себя кареглазым, хотя на самом деле это не так. Но им это неизвестно. Они считают кареглазым меня, себя, а остальных двоих - голубоглазыми. Правильно? При этом каждый из них понимает, что из оставшихся двоих каждый считает себя кареглазым, а другого голубоглазым. При этом каждый из них понимает, что тот, который считает себя кареглазым, а другого голубоглазым, понимает, что тот, которого он считает голубоглазым, не знает своего цвета и тоже по умолчанию считает себя кареглазым.
В общем, нет никакого противоречия между тем, что я вижу трёх голубоглазых людей, и между моими подсчётами, согласно которым каждый из них видит двоих голубоглазых людей, и подсчётами их самих, согласно которым они кареглазы, а остальные голубоглазые видят по одному голубоглазому и т. д.
no subject
Date: 2008-02-13 08:07 pm (UTC)no subject
Date: 2008-02-13 08:15 pm (UTC)no subject
Date: 2008-02-14 08:46 am (UTC)Они думают, что окружающие думают... Как только эти предположения вступают в противоречие с тем, что уж точно видят эти окружающие, сразу вся рекурсия рушится - значит, что в цепочке предположений (я эта рекурсия строится на многих допущениях) есть ложное предположение. Достаточно рассмотреть случай троих голубоглазых, чтобы это увидеть. Мы же всегда говорим о цепочке рассуждений одного туземца - и он обязан оборвать эту цепочку, когда предположения о том, что видит третий туземец приходит в противоречие с реальностью. Это значит, что либо второй (мысленный) туземец ошибся в предположении о своей кареглазости, либо первый (реальный), либо оба. Первый знает, что второй (мысленный) ошибся, и этого достаточно, чтобы отвергнуть эту цепочку. При этом первый туземец ничего не может сказать о цвете своих глаз.
no subject
Date: 2008-02-14 03:06 pm (UTC)no subject
Date: 2008-02-18 11:46 am (UTC)ВОт тут у Вас ошибка ! Если Вы не знаете цвет своих глаз , то как Вы можете исключить себя из числа голубоглазых ? На каком основании ? А если Вы это делаете в виде гипотезы , то каковы Ваши основания считать , что и другие будут принимать ту же гипотезу ?
no subject
Date: 2008-02-18 12:37 pm (UTC)Я не могу знать цвет своих глаз, поэтому гарантированное число голубоглазых для меня включает только тех, которых я вижу. А гарантированное число голубоглазых, которых видит каждый из голубоглазых, которых вижу я, для меня ещё на один меньше. И, по этой смоделированной ситуации, на острове есть голубоглазый, для которого гарантированное число голубоглазых на острове ноль. Он и должен покончить с собой после заявления путешественника. Если самоубийства на первый день не происходит, то эта смоделированная ситуация опровергается действительностью ровно на одно звено. Если на второй день не последовало двух самоубийств, то эта ситуация опровергается действительностью на два последних звена. И так до меня. Если день, соответствующий числу голубоглазых, которых вижу вокруг себя я, не последовало их общее самоубиство, то и мое допущение относительно моего "неголубоглазия" опровергается действительностью, и назавтра я убиваю себя вместе с ними.
no subject
Date: 2008-02-19 11:34 pm (UTC)Далее , тут наблюдается то же самое "логическое зацикливание" , как и в "парадоксе повешенного" , только ещё более грубое . Фактически , всё сводится к чему - делается предположение "другие мыслят так , как я" , а далее я говорю - "если другие мыслят так , как я - то я прав" . Но это же всё равно , что сказать "Х=Х" .
Далее , в Ваших рассуждениях всё основано на том , что если , к примеру , я вижу всего 100 голубоглазых , и на 99 день они не покончили с собой , то я тоже голубоглазый , и должен самоубиться на 100 день . Прекрасно , но что Вы будете делать , если , к примеру , на 23 день вдруг покончат с собой 5 человек ? Или на 98 день покончат с собой 200 человек ? Какие выводы Вы сможете из ЭТОГО сделать ? Я утверждаю , что никакие , и вся цепочка разваливается . Короче , моё мнение - задача некорректна изначально . Я ещё вот тут изложил некоторые возражения по этому же поводу
http://avva.livejournal.com/1873907.html?thread=48569331#t48569331
, так же как и ещё один логически непротиворечивый вариант выхода из этого "парадокса" .
no subject
Date: 2008-02-19 11:59 pm (UTC)А по условию задачи, цвета своих глаз они не знают и узнать не могут, кроме как из слов путешественника.
Если их трое, всё будет точно так же, только трое покончат с собой на третий день. А произвольным их число быть никак не может, поскольку если бы был один голубоглазый, он покончил бы с собой в первый день. Если бы их было двое, они покончили бы на второй и т. д.