об одной хорошей загадке
Feb. 12th, 2008 07:55 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaТерри Тао (гениальный математик) написал в своем блоге запись о известной логической загадке (англ.). В комментариях у него ведутся долгие споры о том, верно ли кажущееся странным и противоречащим интуиции решение этой загадки, причем, что любопытно, на довольно низком уровне, т.е. там многие участники просто не понимают и продолжают нести чушь, хотя другие им пытаются объяснить. Учитывая авторитет автора блога, ситуация выходит несколько комическая, ну как если бы в блоге у Эйнштейна в комментариях какие-то неадекватные личности многословно критиковали принцип "все относительно" с моральной точки зрения.
Мне кажется, что я придумал довольно забавный способ посмотреть немного с другой стороны на решение загадки; по крайней мере мне самому этот аргумент раньше не встречался. Я описал это в комментарии у Тао, но, пожалуй, расскажу и здесь, пересказав вначале загадку и ее решение.
Загадка такая (есть много версий, это одна из них): один остров населен племенем, у членов которого бывают только голубоглазые или с глазами карего цвета. Всего на острове живет 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 жизнями зря, согласно пропорции. Нет уж, надо придумать что-то получше. Ага, знаю...
Моя версия решения загадки, таким образом, состоит в следующем: сразу после заявления чужестранца один из жителей острова, известный одновременно своим умом и жестокостью, немедленно набросится на какого-то голубоглазого жителя (может, есть какой-то из них, кого все ненавидят?), и убьет его на месте. После чего все оставшиеся жители будут жить долго и счастливо. Разве что чужестранцу отрежут язык, скажем, чтобы не болтал почем зря. Я бы их за это не осудил.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2008-02-13 05:01 am (UTC)http://www.nes.ru/russian/about/MassMedia/BremzenSonin-Expert-17-10-05.htm
no subject
Date: 2008-02-13 05:08 am (UTC)no subject
Date: 2008-02-13 05:17 am (UTC)no subject
Date: 2008-02-13 05:19 am (UTC)no subject
Date: 2008-02-13 05:30 am (UTC)no subject
Date: 2008-02-13 05:36 am (UTC)no subject
Date: 2008-02-13 05:36 am (UTC)А вариант про убийство и правда похож на решение проблемы наименьшей кровью...
no subject
Date: 2008-02-13 05:36 am (UTC)Подсказка путешественника несет новую мета-мета-информацию только в том случае, пока какой-нибудь житель может предположить, что хотя бы один человек может думать, что на острове нет голубоглазых. Если голубоглазых четверо, то в воображении А, придумывающего логику дла Б, придумывающего логику дла В, придумывающего логику дла Г, последний в цепочке Г обязательно должен увидеть голубые глаза Б. Тогда сразу начнется отсчет дней до общего самоубийства.
no subject
Date: 2008-02-13 05:43 am (UTC)Так. А как это preview получился отдельным постингом, да ещё и незалогиненным?
no subject
Date: 2008-02-13 05:46 am (UTC)идиотский, но смущающий меня вопрос
Date: 2008-02-13 05:48 am (UTC)Вопрос могу развить, но если ты ответишь мне на этот, думаю, дальше смогу сам допетрить.
Ассоциативное бешенство
Date: 2008-02-13 05:50 am (UTC)Угадай, чем кончилось? :)
Названия не помню, в сети найти не смог.
Re: идиотский, но смущающий меня вопрос
Date: 2008-02-13 05:51 am (UTC)no subject
Date: 2008-02-13 05:54 am (UTC)no subject
Date: 2008-02-13 06:01 am (UTC)А как может быть иначе, если каждый видит как минимум 99 голубоглазых? Каким образом при этом можно не знать о том, что каждый это видит? Т.е. если я житель этого острова, то я знаю, что любой из моих сограждан видит либо 100, либо 99 голубоглазых, и соответственно, знает о том, что голубоглазые существуют.
no subject
Date: 2008-02-13 06:06 am (UTC)no subject
Date: 2008-02-13 06:10 am (UTC)no subject
Date: 2008-02-13 06:11 am (UTC)"С одной стороны, путешественник не сообщил островитянам никакой новой информации. Он сказал им, что среди них есть хотя бы один голубоглазый житель; но каждый из них и так это знал, потому что видел вокруг себя кто 99, кто 100 голубоглазых жителей."
Как я это вижу, путешественник не сообщает _ровно никакой_ новой информации, но он даёт _точку отсчёта_. То есть до этого дня все знали что голубоглазые существуют, но они не могли ни прокого утверждать, что он знает _с этого определённого момента_. Поэтому индуктивная логика не могла быть применена, а после выходки путешественника - может быть применена.
no subject
Date: 2008-02-13 06:12 am (UTC)no subject
Date: 2008-02-13 06:13 am (UTC)no subject
Date: 2008-02-13 06:14 am (UTC)Но допустим, что голубоглазый гражданин не станет обьявлять цвет своих глаз во всеуслышанье, а просто обьявит, что он решил покончить с религией и теперь он узнал цвет своих глаз. Поскольку все сограждане и раньше знали этот цвет, то не будет ли это заявление равносильным приведенному выше и таким образом приведет к тем же последствиям?
no subject
Date: 2008-02-13 06:16 am (UTC)Но и сейчас они не знают этого "с определенного момента" - до этого момента любому точно также было известно, что голубоглазые существуют. Если эти люди живут на острове долго - то известно по крайней мере в течение 200 дней (предположим для простоты, что население острова не меняется :)
no subject
Date: 2008-02-13 06:16 am (UTC)no subject
Date: 2008-02-13 06:17 am (UTC)no subject
Date: 2008-02-13 06:18 am (UTC)