Парадокс голубоглазых островитян

Суть проблемы

Предположим, существовал некий остров, население которого исповедовало странную религию: им было запрещено знать цвет своих глаз. И говорить о цвете глаз кого-то другого тоже. Причём, запрет был столь строгий, что узнавший цвет своих глаз в ближайший полдень должен был публично покончить с собой.

Вариантов цвета глаз у островитян было всего два — голубые и карие.

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

Тронутый их заботой путешественник произнёс прочувствованную речь, которую закончил фразой:

— Я был очень удивлён, встретив здесь у вас, на другом конце света некоторое количество голубоглазых, как и я, людей.

Местных жителей на острове было, для определённости, сто человек. Из них двадцать — голубоглазых. Все жители, разумеется, видели друг друга неоднократно, поэтому знали про глаза каждого другого человека, кроме себя.

Путешественник уехал, однако на беду оказалось, что каждый местный житель острова обладает идеальным логическим мышлением. Поэтому, возможно, информация, переданная путешественником, позволила ему вычислить цвет своих глаз.

Через год путешественник снова вернулся на этот остров. Что он там увидел?

Некоторые оговорки

Поскольку максимально полное изложение данной задачи сделать довольно трудно, то в этой художественной версии следует заранее отбросить все подвохи, типа…

Путешественник солгал
Какие-то местные жители могли подумать, что он солгал
Путешественник путает названия цветов или вообще их не различает
Не все местные жители логичны
Кто-то не расслышал его слова
Кто-то их неправильно понял
И тому подобное

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

Очевидное решение

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

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

Однако голубоглазых туземцев на острове — двадцать человек. То есть каждый однозначно видит минимум девятнадцать голубоглазых. Поэтому путешественник не сообщил им ничего нового — они были и так в курсе, что на острове до фига голубоглазых.

Поэтому все выжили, всё отлично.

Неочевидное рекурсивное решение

Мы уже знаем, что единственный голубоглазый бы наложил на себя руки на следующий день, а если бы их было двое — они бы ушли в мир иной через двое суток.

Однако что бы было, если бы голубоглазых оказалось трое?

Каждый из них догадался бы, что при наличии двоих голубоглазых, они бы умерли на второй день, а поскольку этого не произошло, то он сам — голубоглазый. Соответственно, все трое самоубились бы на третий день.

Видимо, так же должно было бы произойти и с четверыми: каждый бы думал, что, если он не голубоглазый, то оставшиеся трое должны умереть на третьи сутки. Если же они этого не сделали, то он — голубоглазый. Соответственно, все умрут через четыре дня.

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

После этого все оставшиеся поняли бы, что они все — кареглазые, и на двадцать первый день остров бы вымер.

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

Где тут парадокс?

Парадокс тут вот в чём: вроде бы путешественник не сообщил туземцам ничего такого, чего бы они не знали. Все действительно ещё до встречи с путешественником были в курсе, что на острове полно голубоглазых, с чего вдруг озвучивание этой, всем известной информации привело к поголовному суициду?

Если бы мы имели дело с одним голубоглазым, тут понятно: он не знал, что на острове вообще есть голубоглазые, а теперь вдруг узнал. Но когда голубоглазых видели все, то в чём прикол-то?

Если в результате знания о существовании голубоглазых через n итераций следует вычисление цвета собственных глаз, то каким образом путешественник вообще застал этот остров заселённым? Почему все не поубивались задолго до его приезда?

Разрешение парадокса

Чтобы это объяснить, вводится термин «общее знание» (common knowledge). Действительно, и до того все туземцы знали о наличии голубоглазых, однако они не знали, знают ли об этом все остальные.

Во всяком случае, это предполагается в концепции «общего знания».

Давайте посмотрим, как это работает на примере двоих голубоглазых.

Назовём их для определённости А и Б.

До прощальной речи путешественника А знал, что существует как минимум один голубоглазый. Однако А не знал, какого цвета у него самого глаза. Но ему было совершенно понятно, что, если у него глаза — карие, то Б не знает о существовании голубоглазых. Если же — голубые, то Б знает о существовании голубоглазых.

Поэтому у А не было определённости относительно знаний Б.

У Б всё было аналогично: он тоже не был уверен в знаниях А.

Когда же путешественник сообщил о существовании голубоглазых, то А стал точно знать, что Б знает об их существовании, независимо от того, какие у А глаза. Следовательно, если у А глаза карие, то Б должен вычислить свой цвет глаз и убиться на следующий день. Если же он этого не сделал, то А теперь точно знает, что у него глаза — голубые.

Раскрутка рекурсии

Однако в чём состоит «общее знание» в случае с тремя голубоглазыми — А, Б и В? Ведь А видит минимум двоих голубоглазых, поэтому может быть уверен, что Б и В тоже видят минимум одного голубоглазого (если сам А — кареглазый) или двоих (если А — голубоглазый). Что тут вообще может запустить процесс?

Туземец А может рассуждать так…

Про себя я не уверен, какого цвета у меня глаза, однако давайте предположим, что я — кареглазый. Тогда Б должен видеть одного голубоглазого — В, и думать…
- Предположим, что я, Б, — кареглазый. Тогда В должен понять, что голубоглазый — это он и назавтра самоубиться. Если он этого не сделал, то и я тоже — голубоглазый. Мы убьёмся на второй день
Далее, А видит, что на второй день Б и В не самоубились, поэтому понимает, что его предположение о собственной кареглазости неверно, а потому на третий день надо бы самоубиться ему самому. Вместе, конечно, с Б и В, которые аналогичным способом обо всём догадались.

Здесь можно видеть, что путешественник своей речью запускает процесс уже не напрямую, а как бы «на втором уровне вложенности» — там, где А анализирует уже не ситуацию, а возможные рассуждения Б.

Туземец А точно видел перед собой двоих голубоглазых. Однако он не знал, сколько голубоглазых видит Б — возможно, только одного. «И тогда», — думает А, — «Б уже мог бы себе представить, что В видит вообще ноль голубоглазых».

То есть А понимает, что В точно видит минимум одного голубоглазого, но одновременно с тем понимает, что есть случаи (если сам А окажется кареглазым), в которых Б не будет понимать этого про В: ведь если Б — тоже кареглазый, то В не видит ни одного голубоглазого.

В этом контексте путешественник сообщил А, что теперь Б уверен, что В точно знает, что на острове есть хотя бы один голубоглазый туземец.

А теперь четверо

Дальше рассуждения идут по накатанной. Пусть у нас четверо голубоглазых: А, Б, В и Г.

Тогда А рассуждает так:

Предположим, я, А, — кареглазый. Как тогда будет рассуждать Б?
- Я, Б, вижу двоих голубоглазых. Предположим, что у меня карие глаза, как тогда будет рассуждать В?
  - Я, В, вижу одного голубоглазого — Г, и мы с ним оба знаем, что голубоглазые на острове есть. Поэтому либо он того-с сегодня, либо мы оба — завтра
- Если же В с Г не самоубились на второй день, то я, Б, — голубоглазый. Самоубьёмся же на третий день
Если же Б, В и Г не самоубились на третий день, то и я, А, — голубоглазый. Мы все вместе должны самоубиться на четвёртый.

Казалось бы, но ведь все четверо видят минимум троих голубоглазых? Чтобы же хоть кто-то самоубился, он должен видеть максимум одного — ведь только так он мог бы…

…либо сразу же понять, что он — голубоглазый (если он вообще не видит других голубоглазых),
…либо сразу же понять, что вон тот, которого он видит, сразу бы осознал свою голубоглазость, если бы тоже не наблюдал ещё одного голубоглазого.

Однако тут ведь такая ситуация невозможна: каждый из этих четверых точно знает, что остальные трое видят минимум двоих. Как же это работает?

Ну вот, смотрите.

Я, А, вижу троих голубоглазых, но если я сам — кареглазый, то что видит и думает Б?
- Я, Б, вижу двоих голубоглазых, но если я сам — кареглазый, что тогда видит и думает В?
  - Я, В, вижу одного голубоглазого, но предположим, что я — кареглазый, тогда Г должен видеть ноль кареглазых.

Иными словами, ситуация, в которой кто-то видит одного или даже ноль голубоглазых, существует не напрямую, а только в рассуждениях А о рассуждениях Б о рассуждениях В.

Где-то там, в глубине этих рассуждений путешественник как раз и превращает неопределённость в определённость.

И так далее

Поскольку данные рассуждения однотипны, мы их можем повторить с любым количеством голубоглазых. И таким образом мы приходим к мысли, что все N проживающих на острове голубоглазых с неизбежностью покончат с собой через N дней, а в день N+1 самоубьются все остальные.

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

Поэтому многих людей действительно распирает гордость, когда они, наконец, распутывают всю эту рекурсивную логику и — даже если в их душе всё ещё остаются некоторые сомнения в верности этого решения, — спешат поделиться этим неземным наслаждением с другими.

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

В общем, это — прекрасное решение прекрасной задачи.

Жаль, что оно неверное.

О боже мой, а что ещё-то?

Казалось бы, если закрыть глаза на неопределённость приоритетов и ввести «натянутую формулировку», то рекурсия должна работать: ведь даже в обсуждении проблем с приоритетами предполагалось, что она работает. В ней-то где ошибка?

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

Однако есть тонкий нюанс, внимание!

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

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

Поясню на примере.

Туземец А видел вокруг себя одних только кареглазых, но узнал, что на острове есть голубоглазые. Методом исключения он может вычислить, что он — голубоглазый.
Туземец А решил проанализировать рассуждения Б и нашёл некий способ рассуждений, при помощи которого Б, скажем, на девятнадцатый день мог бы узнать, что он, Б, — голубоглазый.

В чём тут разница?

Разница в том, что в первом случае А обладает точным знанием о положении вещей.

Во втором же случае он знает лишь один из возможных способов, которым Б мог бы прийти к некоторому выводу. Однако он не знает наверняка, что Б будет идти к этому выводу именно этим способом.

Возможно, Б будет рассуждать как-то иначе и вычислит свой цвет глаз за другое количество дней.

Тогда вся рекурсия посыплется — ведь там всё основано, на привязке количества самоубившихся к порядковому номеру дня. Если же возможна иная привязка, то А будет знать наверняка только какую привязку выбрал он сам, а про выбранную Б привязку будет не точно знать, а лишь предполагать.

Да, мы пока что нашли способ рекурсивного вычисления к двадцатому дню цвета собственных глаз. Но мы ведь не доказали, что нет иных способов — приводящих к такому же ответу на сороковой или, наоборот, на пятый день.

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

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

Но нет, чтобы такое предположение использовать в доказательстве, надо ещё доказать, что все возможные способы рассуждений приводят к одному и тому же выводу, причём в один и тот же день. Только так можно быть железно уверенным в единстве способа рассуждений.

Ну или, в частном случае, достаточно было бы доказать, что существует всего один способ.

Так ли это?

Давайте проверим.

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

Тут существует всего один вариант рассуждений.

Однако давайте взглянем на двух туземцев. Точнее, взглянем на другой возможный вариант их рассуждений.

Туземец А думает:

Предположим, я, А, — голубоглазый. Как тогда будет рассуждать Б? Например, так.
- Предположим, я, Б, — кареглазый. Тогда голубоглазый А методом исключения вычислит, что он — голубоглазый, и покончит с собой на следующий день. Если же этого не произойдёт, я пойму, что я тоже голубоглазый и покончу с собой на второй день.
Если Б покончит с собой на второй день, то я, А, пойму, что я — голубоглазый. И покончу с собой на третий день.

Заметьте, этот вариант тоже приводит А к однозначному установлению цвета своих глаз. Равно как и тот, который рассматривался в решении ранее. Однако в этом варианте А покончит с собой только на третий день, а не на второй.

Условие соблюдено: если А может вычислить свой цвет глаз, то он его вычисляет. Но в постановке задаче ведь не говорится, что он должен вычислить это максимально быстрым способом. Да, он мог бы вычислить это и на второй день тоже — предположив свою кареглазость и убедившись на опыте, что это не так. Однако ничто в условиях не обязывает его поступить именно так.

При этом А не находится в каком-то выделенном положении: Б ведь мог бы рассуждать ровно так же, как и А, и А об этом знает.

И А должен учесть такую возможность в своих рассуждениях:

Предположим, я, А, — голубоглазый. Как тогда будет рассуждать Б? Например, так.
- Предположим, я, Б, — голубоглазый. Как бы тогда рассуждал А?
  - Предположим, я, А, — кареглазый. Тогда голубоглазый Б методом исключения вычислит, что он — голубоглазый, и покончит с собой на следующий день. Если же этого не произойдёт, я пойму, что я тоже голубоглазый и покончу с собой на второй день.
- Если А не покончит с собой на второй день, то я, Б, пойму, что я — голубоглазый. И покончу с собой на третий день.
Если Б покончит с собой на третий день, то я, А, пойму, что я — голубоглазый и покончу с собой на четвёртый день.

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

Однако самое главное тут, что ни А, ни Б, не могут точно знать, какой из бесконечного количества этих вариантов выберет другой. И при этом А точно знает, что Б не может знать точно, какой вариант выберет А, а Б точно знает, что А не может точно знать, какой вариант выберет Б.

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

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

Подвох в рекурсии

Где-то между строк рекурсивного метода затерялось неявное приравнивание «знания» и «предположения о ходе рассуждений другого». При наличии же нескольких вариантов рассуждений, дающих тот же вывод о цвете своих глаз, но за разное время, предположение о выбранном варианте остаётся лишь предположением: его нельзя считать точным знанием А о мыслительной модели Б — на том лишь основании, что А известен один из возможных вариантов того, как мог бы рассуждать Б.

Чтобы островитяне знали точно варианты рассуждения друг друга, в постановку задачи следовало бы внести что-то вроде: «все туземцы, если есть такая возможность, обязаны вычислить цвет своих глаз максимально быстро и точно знают, что все остальные туземцы делают так же и точно знают всё это про всех остальных туземцев».

В такой формулировке всё население острова как бы начинает стремиться к массовому самоубийству при первом же к тому поводе.

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

Две ошибки

Итого, красивое решение красивой задачи содержит минимум две ошибки: неопределённость в приоритетах правил и неверное предположение о том, что вариант рассуждений всего один, а потому его можно считать «точным знанием».

В результате, к условию задачи следует добавить ещё два положения:

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

Разумеется, с такими дополнениями ситуация на острове становится совсем какой-то уж заведомо суицидальной, что разрушает всю художественность повествования.

Поэтому имело бы смысл превратить эту формулировку в более правдоподобный и одновременно с тем корректный вариант. Благо, она тоже встречается, причём иногда её тень проскальзывает даже в варианте с островитянами.

Мудрецы в колпаках

Султан как-то раз решил испытать своих мудрецов. Он сказал:

«На каждого из вас наденут синий или красный колпак и запрут каждого в своей комнате.

После этого каждому из вас скажут, на ком какого цвета колпак, но какой на вас не скажут. И посмотреть на него вы тоже не сможете.

К каждому из вас в полдень будет приходить стражник, которому вы можете сказать, какого цвета на вас колпак. Если хоть кто-то ошибётся, то всех вас казнят. Того же, кто угадает цвет своего колпака, отпустят.

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

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

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

Вот тут, да, рекурсивный метод правда сработает, поскольку мудрецы могут договориться о едином способе рассуждений.

Впрочем, у них есть и более простой и понятный алгоритм:

Если никого пока что не отпустили, то каждый должен помнить количество красных колпаков — N, о которых ему сообщили, и в день под номером N сказать, что на нём красный колпак.
Если же мудрец узнал, что кого-то уже отпустили, он должен сказать, что на нём синий колпак.

Почему это работает? Мудрецы в красных колпаках знают об N красных колпаках, те же, на ком синий, — о N+1 красном колпаке. Соответственно, при таком алгоритме есть гарантия, что мудрецы в синем колпаке заявят о цвете своего колпака позже, чем мудрецы в красном. В день N все мудрецы в красных колпаках будут точно знать, что никто не знал о меньшем количестве красных колпаков, чем каждый из них — иначе об этом бы уже сказали. Мудрецы же в синих колпаках будут точно знать, что на них синий, поскольку все мудрецы в красном уже отпущены.

Мудрецы в колпаках без права на переговоры

Теперь предположим, что султан не дал мудрецам возможности посовещаться, а сразу запустил процесс.

В этом случае ситуация становится гораздо менее надёжной. Однако каждый мудрец знает, что другие мудрецы не желают быть казнёнными и хотели бы выйти как можно быстрее. Поэтому каждый из них мог бы предположить, что все остальные выберут наискорейший вариант безопасного вычисления цвета своего колпака: либо с рекурсивными рассуждениями, как в задаче про островитян, либо в виде «упрощённого алгоритма», как в предыдущем разделе.

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

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

То есть, если ты знаешь, что мудрецов — сто, а красных колпаков — двадцать, то быстрее всего можно выйти, если в алгоритм подставить красные колпаки. И все остальные, видимо, об этом догадаются, поскольку они тоже знают либо о двадцати, либо о двадцати одном, либо о девятнадцати красных колпаках.

Проблема наступает тогда, когда синих и красных колпаков примерно половина плюс—минус один.

Тут уже придётся, видимо, искать какую-то иную зацепку, вероятность нахождения которой высока и для других мудрецов тоже. Из очевидных же зацепок тут только то, что султан сказал «красные и синие колпаки» — именно в таком порядке. То есть надо выбрать красный, надеясь, что и остальные тоже ухватятся за эту единственную зацепку.

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

В чём же отличие от ситуации с островитянами?

Мудрецы не хотят умирать и островитяне, видимо, тоже, однако отличие между ними в том, что те условия, которые позволяют мудрецам сохранить жизнь, напротив, приводят к смерти островитян.

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

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

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

Однако запрета на это нет, что тоже снимает целый ряд неопределённостей, которым была посвящена изрядная часть статьи.

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

Хотя и не таким шокирующим, а потому не так сильно поражающим.