Перед вами головоломка по эпистемической логике. Для ее решения не требуется знакомства с предыдущими публикациями. Материал продолжает перевод статьи Джоэла Дэвида Хэмкинса «Epistemic Logic and the Problem of Common Knowledge». Ранее вышли:
На отдалённом острове живут сто безупречно логичных жителей с отличным зрением, и каждый из них знает, что все остальные обладают такими же способностями. Кроме того, у всех них яркие, насыщенно-голубые глаза.
Однако по их культурным обычаям цвет глаз никогда не обсуждается. Если кто-либо из жителей узнает, что у него голубые глаза, он обязан на следующем рассвете покинуть остров, устроив перед уходом эффектное представление, заметное всем остальным жителям. Поэтому на острове нет ни зеркал, ни камер, а сами островитяне никогда не смотрят на собственное отражение. И действительно, никто из них не знает цвета собственных глаз.
Однажды на остров приезжает гостья, которой все доверяют, и приятно проводит там некоторое время. В конце своего визита, перед отъездом, когда всё сообщество собирается её проводить, она замечает:
“По крайней мере у одного из вас голубые глаза”.
Ровно через сто дней происходит следующее: на рассвете все островитяне устраивают большое эффектное представление и покидают остров.
Почему? Можете объяснить, каким образом каждый из островитян именно в этот день пришёл к знанию того, что у него голубые глаза?
Отступление
Давайте решим эту задачу вместе. Для начала полезно разобрать несколько более простых случаев.
Сначала рассмотрим тривиальный случай, когда голубые глаза есть только у одного жителя острова, а не у ста. Когда гостья, которой все доверяют, говорит: “По крайней мере у одного из вас голубые глаза”, единственный голубоглазый островитянин, естественно, заключает, что речь может идти только о нём. Поэтому на рассвете следующего дня он устраивает эффектное представление перед уходом и покидает остров.
Теперь рассмотрим случай, когда на острове всего два жителя и у обоих голубые глаза. Каждый из них, разумеется, знает, что у другого голубые глаза, но поначалу не знает цвета собственных глаз. Услышав от гостьи, что по крайней мере у одного из них голубые глаза, каждый рассуждает следующим образом: “Если у меня глаза не голубые, то другой островитянин это знает. А поскольку он только что узнал, что по крайней мере у одного из нас голубые глаза, он поймёт, что голубые глаза именно у него. Тогда на следующем рассвете он устроит эффектное представление и покинет остров”.
Когда на следующий день никакого представления не происходит, оба продолжают рассуждать: “Раз другой островитянин не устроил эффектного представления и не покинул остров, значит, причина в том, что у меня самого голубые глаза, а он, в свою очередь, ждал, не устрою ли такое представление я”.
Таким образом, установив цвет собственных глаз, оба островитянина на рассвете второго дня устраивают эффектное представление и покидают остров.
В случае трёх островитян каждый из них рассматривает возможность того, что у него самого глаза не голубые. Поскольку у двух остальных глаза голубые, при таком предположении каждый ожидал бы, что эти двое пройдут через рассуждение из случая с двумя островитянами. А именно, каждый из них видел бы одного другого голубоглазого островитянина и задавался бы вопросом, голубые ли глаза у него самого. Если бы нет, то другой островитянин устроил бы эффектное представление уже на первом рассвете. Но этого не происходит, поскольку на самом деле каждый видит двух людей с голубыми глазами. Следовательно, оба должны были бы понять, что у них голубые глаза, и устроить эффектное представление на втором рассвете.
Однако и этого не происходит, поскольку все трое ждут, не поступят ли так двое остальных. Поэтому теперь каждый из них понимает, что у него самого тоже голубые глаза. В результате все трое устраивают эффектное представление на третьем рассвете после объявления.
И так далее для большего числа островитян. Общее утверждение, которое я докажу по индукции, состоит в следующем: если на острове есть n голубоглазых жителей и, возможно, некоторое число жителей с глазами другого цвета, то все голубоглазые жители узнают цвет своих глаз к рассвету n-го дня после объявления, устроят эффектное представление и покинут остров в этот день.
Мы уже показали, что это верно при n = 1. Предположим теперь, что утверждение верно для n, и рассмотрим случай с n + 1 голубоглазыми островитянами. Каждый из них допускает, что его собственные глаза, возможно, не голубые. Тогда на острове было бы ровно n голубоглазых жителей, а значит, каждый ожидал бы, что все остальные голубоглазые жители устроят эффектное представление и покинут остров на n-й день.
Но этого не происходит, поскольку каждый из них сам ждёт, не сделают ли это остальные. Поэтому каждый островитянин заключает, что его глаза всё-таки голубые. Поскольку все n + 1 голубоглазых жителей независимо приходят к такому выводу, на рассвете (n + 1)-го дня они все устраивают эффектное представление и покидают остров.
Следовательно, по индукции утверждение доказано для всех n, и в частности для n = 100, как в нашей задаче. Таким образом, задача решена.
Тонкий парадокс
Обратите внимание, что утверждение гостьи: “По крайней мере у одного из вас голубые глаза” — к тому моменту уже было известно каждому из островитян. Но как получается, что публичное объявление факта, который и без того известен каждому, запускает сложную цепочку рассуждений, в конечном счёте приводящую к их печальному изгнанию?
Дело в том, что для рассуждений островитян важен не только сам факт, высказанный гостьей, но и то, что каждый островитянин знает, что остальные тоже знают этот факт, а также знает, что все знают, что все его знают, и так далее — с повторением этой вложенности сто раз. Иными словами, существенным оказалось то, что факт наличия голубых глаз по крайней мере у одного из островитян стал общим знанием.
ссылка на оригинал статьи https://habr.com/ru/articles/1076964/