об одной хорошей загадке
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-17 03:31 am (UTC)"Действительно, с самого начала каждый туземец знает, что есть один кареглазый, а один голубоглазый, но он не знает, что это знает любой другой туземец."
если каждый знает то почему он не знает что любой другой каждый знает
чем это отличается от задачи когда 10 человек в комнате в кружок с красными или синими метками на лбу
нужно догадаться какая у тебя метка и получить приз
говорить понятное дело нельзя
если количество меток любого цвета >1
то какую новую информацию привнесет голос из динамика - ребята среди вас есть красная метка - каждый и так видит или по крайней мере одну красную метку
no subject
Date: 2008-02-17 05:35 am (UTC)Потому что из того, что он видит n-голубоглазых он не может сделать вывод, что все видят n-голубоглазых. Прочитайтей, пожалуйста, про индуктивное доказательство по ссылке.
прочел , по прежнему
Date: 2008-02-17 05:43 am (UTC)то есть по крайней мере одного голубоглазового если n>1
именно это и сообщил чужой
Re: прочел , по прежнему
Date: 2008-02-17 05:55 am (UTC)Вот-вот, соответственно он не может быть уверен в том, что каждый, кто видит n-1 blue уверен в том, что один из этих blue видит по крайней мере n-1 blue.
Re: прочел , по прежнему
Date: 2008-02-17 06:08 am (UTC)почему не может?
я прочел вашу ссылку
может вы что-то пропустили или я что то важное пропустил
сократим количество участников до скажем 10 из них голубых до 3 для удобства
скажем я blue
я вижу 7 brown and 3-1=2 blue
любой brown видит 7-1=6 brown and 3 blue
в каждом случае поскольку я - blue- вижу по крайней мере 2 blue - я могу утвержать что любой видит по крайней мере один blue
то есть при условии что каждый участник видит по крайней мере 2 blue общее количество blue = от 3 и выше
итого - вношу поправку в предыдущий комент - при условии что n>2 - чужой ничего нового не сказал потому как - опять же - если каждый видит по крайней мере 2 blue, он может быть уверен что любой видит по крайней мере 1 blue
что нового сказал чужой?
Re: прочел , по прежнему
Date: 2008-02-17 06:33 am (UTC)мальчика феноменальная памятьу туземцов идеальные индуктивные способности. Если туземец полагает, что другой туземец видит одного голубоглазого, то он рассуждает за тех туземцов, которые видят одного голубоглазого следующим образом. Так, я вижу blue, но если я brown, то голубоглазый видит только кареглазых. И последний не может тчоно знать, что существует голубоглазый. Соответственно, чувак, который видит одного голубоглазого не уверен в том, что он знает о существовании голубоглазого. И он не может быть уверен в том, что все туземцы знают, что другие туземцы уверены в существовании голубоглазого Это и есть знание! Соответственно не может быть уверен и тот, который видит двух! Потому что он думает, что тот, кто-то может видеть одного, и думать про него, что он знает.... И если это рассмотреть по индукции будет верно для любого количество голубоглазых.Прочтите это внимательно :-)
Re: прочел , по прежнему
Date: 2008-02-17 06:53 am (UTC)Re: прочел , по прежнему
Date: 2008-02-17 06:53 am (UTC)Re: прочел , по прежнему
Date: 2008-02-17 07:00 am (UTC)Re: прочел , по прежнему
Date: 2008-02-17 07:08 am (UTC)или вы усложняете
на вашем методе индукции я ломаюсь на третьем
утром перечитаю
Re: прочел , по прежнему
Date: 2008-02-17 07:19 am (UTC)Re: прочел , по прежнему
Date: 2008-02-17 07:20 am (UTC)sorry