avva | об одной хорошей загадке

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

Мне кажется, что я придумал довольно забавный способ посмотреть немного с другой стороны на решение загадки; по крайней мере мне самому этот аргумент раньше не встречался. Я описал это в комментарии у Тао, но, пожалуй, расскажу и здесь, пересказав вначале загадку и ее решение.

Загадка такая (есть много версий, это одна из них): один остров населен племенем, у членов которого бывают только голубоглазые или с глазами карего цвета. Всего на острове живет 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 жизнями зря, согласно пропорции. Нет уж, надо придумать что-то получше. Ага, знаю...

Моя версия решения загадки, таким образом, состоит в следующем: сразу после заявления чужестранца один из жителей острова, известный одновременно своим умом и жестокостью, немедленно набросится на какого-то голубоглазого жителя (может, есть какой-то из них, кого все ненавидят?), и убьет его на месте. После чего все оставшиеся жители будут жить долго и счастливо. Разве что чужестранцу отрежут язык, скажем, чтобы не болтал почем зря. Я бы их за это не осудил.