Перед вами головоломка по эпистемической логике. Для ее решения не требуется знакомства с предыдущими публикациями. Материал продолжает перевод статьи Джоэла Дэвида Хэмкинса «Epistemic Logic and the Problem of Common Knowledge». Ранее вышли: 

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

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

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

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

«По крайней мере у одного из вас голубые глаза».

Ровно через сто дней происходит следующее: на рассвете все островитяне устраивают большое эффектное представление и покидают остров.

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

Отступление

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

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

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

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

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

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

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

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

Мы уже показали, что это верно при n = 1. Предположим теперь, что утверждение верно для n, и рассмотрим случай с n + 1 голубоглазыми островитянами. Каждый из них допускает, что его собственные глаза, возможно, не голубые. Тогда на острове было бы ровно n голубоглазых жителей, а значит, каждый ожидал бы, что все остальные голубоглазые жители устроят эффектное представление и покинут остров на n‑й день.

Но этого не происходит, поскольку каждый из них сам ждёт, не сделают ли это остальные. Поэтому каждый островитянин заключает, что его глаза всё‑таки голубые. Поскольку все n + 1 голубоглазых жителей независимо приходят к такому выводу, на рассвете (n + 1)‑го дня они все устраивают эффектное представление и покидают остров.

Следовательно, по индукции утверждение доказано для всех n, и в частности для n = 100, как в нашей задаче. Таким образом, задача решена.

Тонкий парадокс

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

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