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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

И так далее

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

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

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

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

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

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

Продолжение следует.