Предыдущий пост Поделиться Следующий пост
Парадокс голубоглазых островитян
lex_kravetski


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



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

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

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

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

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

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

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

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


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



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

  1. Путешественник солгал


  2. Какие-то местные жители могли подумать, что он солгал


  3. Путешественник путает названия цветов или вообще их не различает


  4. Не все местные жители логичны


  5. Кто-то не расслышал его слова


  6. Кто-то их неправильно понял


  7. И тому подобное


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

Мы вместо этого будем рассматривать некий идеальный случай.


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



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

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

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

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


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



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

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

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

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

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

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

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


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



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

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

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


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



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

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

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

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

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

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

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

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


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



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

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

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


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


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


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

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

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

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


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



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

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

  • Предположим, я, А, — кареглазый. Как тогда будет рассуждать Б?


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


      • Я, В, вижу одного голубоглазого — Г, и мы с ним оба знаем, что голубоглазые на острове есть. Поэтому, либо он того-с сегодня, либо мы оба — завтра.


    • Если же В с Г не самоубились на второй день, то я, Б, — голубоглазый. Самоубьёмся же на третий день.


  • Если же Б, В и Г не самоубились на третий день, то и я, А, — голубоглазый. Мы все вместе должны самоубиться на четвёртый.


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

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


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


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

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

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


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


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


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

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


И так далее



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

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

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

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

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

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



doc-файл



Первая часть в блоге автора
Первая часть на сайте «XX2 Век»



Вторая часть в блоге автора
Вторая часть на сайте «XX2 Век»



Третья часть в блоге автора
Третья часть на сайте «XX2 Век»



Есть ещё вариант:
Я не знаю какой цвет моих глаз, не стараюсь об этом узнать и не рефлексирую по этому поводу.

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

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

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

Edited at 2018-05-28 15:24 (UTC)

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

Тут вроде как похоже на доказательство по индукции.

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

Для 1,2,3 доказали и думают, что достаточно. А вот для n и n+1 не доказано однозначно, поэтому возникают проблемы.

Тут прямо по построению рассуждений каждый следующий шаг n+1 опирается на предыдущий шаг n. Иначе рассуждение не было бы рекурсивным.

Чем-то напоминает историю про Ахиллеса и черепаху: никогда не догонит; все убьются :-) Чую, что  бесовщина, но обосновать не могу (с)


массовый суицид на 21-й день произошел.

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

А с какого фига они этого не знали?

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

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

1) Я сам вижу на острове 19 человек с голубыми глазами, то есть я знаю, что на острове минимум 19 голубоглазых.
2) Я знаю, что любой другой островитянин знает: на острове минимум столько голубоглазых, сколько он видит сам.
3) Если я голубоглазый, то любой другой голубоглазый видит столько же голубоглазых, сколько и я (а любой кареглазый - даже больше, чем я). Если я кареглазый, то другие кареглазые видят столько же голубоглазых, сколько я, а любой голубоглазый - на одного меньше (поскольку не видит себя), то есть 18.
3.1) То есть, я знаю, что _любой_ человек на острове видит как минимум 18 голубоглазых. И, соответственно, знает, что их минимум столько имеется.
4) Теперь я поставлю себя на место того гипотетического голубоглазого островитянина, который видит минимум 18 голубоглазых. Построив цепочку рассуждений так же, как и я, он придет к выводу: любой человек на острове видит как минимум 17 голубоглазых и знает об их существовании.
5) А больше нам никуда спускаться и не надо:
- Я знаю, что на острове как минимум 19 голубоглазых
- Я знаю, что каждый знает, что на острове как минимум 18 голубоглазых
- Я знаю, что каждый знает, что каждый другой знает, что на острове как минимум 17 голубоглазых.
6) Поскольку и 19, и 18, и 17 больше нуля, это можно переформулировать:
- Я знаю, что на острове есть голубоглазые
- Я знаю, что _каждый_ знает, что на острове есть голубоглазые
- Я знаю, кто _каждый_ знает, что _каждый_ знает.

Следовательно:
- Путешественник не сказал мне ничего нового
- Я знаю, что путешественник _никому_ не сказал ничего нового
- Я знаю, что _все_ знают, что путешественник _никому_ не сказал ничего нового.

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

> Построив цепочку рассуждений так же, как и я, он придет к выводу: любой человек на острове видит как минимум 17 голубоглазых и знает об их существовании.

Ну а потом он подумает о том, как думал бы этот «любой человек»: «я вижу минимум 17 голубоглазых, однако если я кареглазый, то любой человек видит минимум 16 голубоглазых, попробую представить себе, как он в этом случае рассуждает…».

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

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

Путешественник не сказал, сколько именно голубоглазых — только что их больше нуля.

"И до того все туземцы знали о наличии голубоглазых, однако они не знали, знают ли об этом все остальные" - как такое возможно? То есть, каждый туземец предполагал, что все его соплеменники могут быть слепыми?
Каждый зрячий голубоглазый знал, что на острове 19 или 20 голубоглазых, кареглазый - что их 20 или 21. И всё. На каком основании он бы взялся рассуждать: "Если бы нас было двое... или трое...", если он ежедневно видит около двух десятков?

Про то, как именно обстоят дела со знанием, объясняется в конце раздела «А теперь четверо».

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

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

P.S. Для моих рассуждений необходимо, чтобы островитяне умели считать. По крайней мере достаточно, чтобы произвести счёт меньшей по численности группы (группировка соответственно по цвету глаз).

Edited at 2018-05-29 09:01 (UTC)

Путешественник им не сказал, сколько всего голубоглазых — только что они вообще есть.

Нет ли здесь смешения логик разных порядков?

Edited at 2018-05-29 16:32 (UTC)

Хм. Логика рассуждений выходит примерно следующая:

0. Пусть голубоглазых 4.

1. Я вижу, что голубоглазых 3 или 4.
2. Если я кареглазый, то другие голубоглазые видят, что голубоглазых 2 или 3. То есть, в этом случае я буду знать, что N=3, но у них ещё будет неопределённость.
3. Один из этих 3 голубоглазых будет думать:
3.1. Я вижу, что голубоглазых 2 или 3.
3.2. Если я кареглазый, то другие голубоглазые видят, что голубоглазых 1 или 2. То есть, я буду знать, что их 2, но у них сохраняется неопределённость.
3.3. Один из этих 2 голубоглазых будет думать:
3.3.1. Я вижу, что голубоглазых 1 или 2. (*)
3.3.2. Если я кареглазый, то оставшийся голубоглазый видит, что голубоглазых 1 (он сам) или 0.
3.3.3. Значит, он знает, что говорили только про него, и завтра в полдень убъёт себя.
3.3.4. Он себя не убил, значит, он видел, что голубоглазых на самом деле 1 или 2, то есть я тоже голубоглазый, и завтра в полдень должен себя убить.
3.4. Он себя не убил, значит, он видел, что голубоглазых на самом деле 2 или 3, то есть я тоже голубоглазый, и завтра в полдень должен себя убить.
4. Он себя не убил, значит, он видел, что голубоглазых на самом деле 3 или 4, то есть я тоже голубоглазый, и завтра в полдень должен себя убить.


Однако, на максимальной глубине вложенности (*) (да и вообще начиная со второго уровня вложенности) островитянин якобы рассуждает, что он видит 1 или 2 голубоглазых. Но он заведомо видит не менее 3 голубоглазых. Противоречие.

Ну как, оно? Или это у меня где-то ошибка в рассуждениях.

Уточнение: да, в статье это рассматривается. И мне кажется, что именно в этом и ошибка — в рассуждениях А о рассуждениях Б о рассуждениях В В по-прежнем должен видеть не менее трёх голубоглазых.

Другой подход — через common knowledge, то самое очевидное решение. Перепишу.

Если голубоглазый один — он вообще не знает о существовании голубоглазых, и путешественник сообщает ему новую информацию.

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

Если голубоглазых трое или больше, то все заведомо знают (common knowledge), что все остальные видят хотя бы одного голубоглазого, и путешественник новой информации не сообщил.

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

Если голубоглазых четверо...

Всё-таки индукция.

Edited at 2018-05-30 10:07 (UTC)

Эх Лекс красавец.
Вопрос про индивидуальные и коллективгые стратегии.
В текущей постановке задача требует уточнения стартовых условий.


Хитрость тут вот в чём:
Индуктивные рассуждения показывают, что "если на утро дня N ты видишь N-1 голубоглазых" -- правильная стратегия убивать себя.
Дедуктивные рассуждегия "back propagation" -- поавильность этой стратегии не подтверждают.
Что же делать, какую стратегию выбрать.

1. Абориген находит индуктивное решение задачи (стратегию "убивпй себя на N+1 день" -- да
2. Может ли абориген считать день "Ч" днём отсчёта -- да, т.к. обретает смысл база индукции
3. Абориген обнаруживает, что дедуктивное решение никак задачу не решает
4. Абориген спрашивает: есть ли другие прецеденты, когда логическая задача решалась одним способом и не решалась другим -- да есть
5. Абориген споашивает: дизавуирует ли наличие бесполезного (дедуктивного) метода наличие полезного индуктиного -- нет, индуктивное решение в силе
6. Абориген спрашивает: какой коллективной стратегии следует придерживаться группе -- и это ключевой вопрос морали папуасов. Что является обманом: "не найти решение, когда было бы можно скооперироваться" или "найти решение, когда было бы можно не искать"

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

Нет начало похоже, но 4сть нюанс:
1. Для 3х человек существ2ет только 1 чистая стратегия, для 5 уже две (4 лень считать).
2. Мудрецам заведомо выгодно кооперировкться и они решили бы эту задачу; выгодно ли кооперироваться пап2асам мы по условию задачи не знаем -- и поэтому не знаем решт ли они задачу.

*) предполагаем, что папуасы владеют рефлексией 2го рода.

?

Log in

No account? Create an account