The_Searcher Голосов: 4 Адрес блога: http://www.liveinternet.ru/users/the_searcher/ Добавлен: 2007-11-28 15:41:09 блограйдером the_searcher

Ответ на задачу о голубоглазых островитянах

2012-08-23 11:52:02 (читать в оригинале)

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

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

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

До высказывания европейца знание о наличии голубоглазых не было "общепринятым знанием". Один не знал бы об этом вообще, двое знали бы, но не знали бы - знает ли об этом другой, трое не знали бы знают ли все, что все знают, что все знают об этом и т.д. Для 100 островитян это цепочка из 100 "знают что", а публичное объявление делает её бесконечной.

"Общепринятое знание" это когда не только все в группе что-то знают, но и все знают, что все это знают, а так же все знают о том, что все знают, что все это знают - и так далее до бесконечности. Оно введено Дэвидом Льюисом (David Kellogg Lewis) в 1969 году. Сам же раздел науки называется "эпистемальная модальная логика" - в ней изучается модальная логика по отношению к знаниям. Примеры модальностей: необходимо/возможно/случайно или всегда/иногда/никогда и т.д. Это направление признано и активно развивается, пожалуй, лишь в последний десяток лет, после того как за работу в этом направлении была вручена нобелевская премия по экономике.

Эту задачу сформулировал ещё Герберт Гинтис в 2000 году в своей книге "Развитие теории игр" (Herbert Gintis "Game Theory Evolving"), как задачу о женщинах Севитана (The Women of Sevitan). Там вместо цвета глаз - мужья этих женщин, которые изменяют или не изменяют. А когда женщина узнаёт об изменах мужа, она рисует ему на затылке красную букву И (изменник) ночью, пока он спит. Вся деревня знает изменников, кроме их жён.

Прообразом же этой задачи стала притча про трех барышень, едущих в поезде. У всех троих лица измазаны сажей, но каждая видит лишь двух других и смеется. И вдруг самая умная из них, скажем, Анна, перестает смеяться, понимая, что и у нее лицо перепачкано. Она рассуждает так: "Если бы мое лицо не было испачкано, то Бетти, глядя на смеющуюся Веронику, догадалась бы, что та смеется над ней, и сама перестала бы смеяться; но она не перестает, значит, мое лицо тоже в саже".

Очень рекомендую интересную и доступную статью по теме: Шантаж, блеф и чумазые девушки. НОБЕЛЬ–2005 ПО ЭКОНОМИКЕ

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