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

[sergey zhukov]

В интересной книжке Метта Кука “Ловкость ума” прочитал следующий парадокс:

На острове проживает очень суеверное племя. Оно состоит из 1000 соплеменников: 900 с карими глазами и 100 с голубыми глазами. На острове нет отражающих поверхностей (даже воды), поэтому ни один из соплеменников не может видеть цвет своих собственных глаз, но каждый соплеменник может видеть любого другого соплеменника и соответственно подсчитывать цвета глаз. Говорить о чьем-либо цвете глаз запрещено, поэтому член племени никогда не узнает цвет своих глаз от кого-то другого. Любой член племени, который каким-то образом узнает свой собственный цвет глаз, совершит ритуальное самоубийство в полдень следующего дня на открытой площади, чтобы все могли его увидеть. Каждый член племени является идеальным логиком, а это значит, что он немедленно сделает любое логически выводимое заключение. Каждый член племени знает всю информацию, содержащуюся в этом условии головоломки. В течение многих лет племя жило в гармонии. Никто не по кончил жизнь самоубийством. Однажды исследователь (скажем, с зелеными глазами) высаживается на острове, не подозревая о местном суеверии, и на общем собрании племени во всеуслышание заявляет: «Замечательно видеть в этой части света по крайней мере одного человека с голубыми глазами». Какое влияние его заявление окажет на население острова?

Утверждается, что правильный ответ: все голубоглазые (Г) должны покончить с собой через 100 дней. Рассуждение следующее.

Предположим для начала, что Г на острове только один. После такого заявления он понимает, что “по крайней мере один Г” – это он (поскольку других Г он не видит). Поэтому на следующий день он должен совершить самоубийство.

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

Добавка сюда третьего Г приведет к тому, что “озарение” приходит к всем трем через три дня и т.д. Поэтому если Г сто, то через сто дней все они покончат с собой.

Парадокс же заключается в том, что этот зеленоглазый исследователь ведь на самом деле не сообщил островитянам ничего нового. Все и без него прекрасно видели, что на острове есть по крайней мере один Г. Почему его заявление оказало такое влияние? Мог ли то же самое (с тем же эффектом) заявить один из островитян?

[EUgeneUS]

Общее знание

[Parkhomuk]

sergey zhukov
Ерунда какая-то, у Вас же сказано

sergey zhukov в сообщении #1725131 писал(а):

на общем собрании племени

, в то же время

sergey zhukov в сообщении #1725131 писал(а):

Оно состоит из 1000 соплеменников: 900 с карими глазами и 100 с голубыми глазами

и

sergey zhukov в сообщении #1725131 писал(а):

Каждый член племени является идеальным логиком

и

sergey zhukov в сообщении #1725131 писал(а):

Каждый член племени знает всю информацию, содержащуюся в этом условии головоломки

мне видится, что тут не нужен никто посторонний, и массовое ритуальное самоубийство должно произойти прямо сейчас (ну или я не идеальный логик :()

sergey zhukov в сообщении #1725131 писал(а):

На острове нет отражающих поверхностей (даже воды)

По моему парадокс в этом :)

[wrest]

sergey zhukov в сообщении #1725131 писал(а):

Каждый член племени знает всю информацию, содержащуюся в этом условии головоломки.

Тогда каждый знает и цвет своих глаз, т.к. видит цвет глаз всех остальных. В сумме же должно быть 999=899+100 соплеменников для кареглазых и 999=900+99 для голубоглазых. Не нужно ничего ждать, всё ясно сразу.

[DimaM]

Похоже на не вполне удачную попытку перефразировать известную загадку про мудрецов и изумруды.

[wrest]

Хорошо, допустим на 100-й день все голубоглазые померли. Но тогда на 101й день помрут и все остальные, т.к. поймут, что остались только кареглазые. Острову конец.

Вычитал тут.

Автор: Winkler, Peter
Название:  Mathematical mind-benders
Перевод названия: Математические закручки
ISBN: 9781568813363

стр. 95-97

Допустим, на острове всего три соплеменника, и все трое голубоглазые.
А посетитель говорит им "На острове только кареглазые" (т.е. заведомую неправду, причем все сполеменники немедленно знают что это неправда).
Тогда все трое в итоге решат, что знают свой цвет глаз, и племени кирдык.

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

[sergey zhukov]

wrest в сообщении #1725134 писал(а):

Тогда каждый знает и цвет своих глаз

Хе...хе... Нет, общее количество голубоглазых и кареглазых им, конечно, не должно быть неизвестно. Т.е. каждый его знает с точностью до 1 человека.

-- добавлено через 2 минуты --

wrest в сообщении #1725141 писал(а):

Тогда все трое в итоге решат, что знают свой цвет глаз.

И как они это решат? Ведь противоположность - это "на острове не только кареглазые", куда входит и "все голубоглазые" и "два голубоглазых и один кареглазый". Что из этого можно вытащить?

[wrest]

sergey zhukov в сообщении #1725145 писал(а):

И как они это решат?

На 3й день каждый поймёт что он голубоглазый.

[sergey zhukov]

wrest
Что-то я не догадываюсь, как они рассуждают. А если изначално был один кареглазый, то что тогда? Тоже догадаются правильно?

[mihaild]

sergey zhukov
Да. ИМХО лучший по соотношению наглядности/неинтуитивности случай с тремя людьми.
Пусть у нас трое голубоглазых (кареглазые не важны), Вася, Петя и Сережа. Они все знают, что есть голубоглазые. Кроме того, Вася знает, что Петя знает, что есть голубоглазые.
Но вот уже Сережа не знает, что Вася знает, что Петя знает, что есть голубоглазые. С точки зрения Сережи, может быть, что у него глаза карие, тогда Вася может думать, что у Васи тоже глаза карие, и в этой ситуации Петя не будет знать, что есть голубоглазые.
А вот после высказывания логика Сережа уже точно знает, что Вася знает, что Петя знает, что есть голубоглазые.

[wrest]

sergey zhukov в сообщении #1725145 писал(а):

Ведь противоположность - это "на острове не только кареглазые", куда входит и "все голубоглазые" и "два голубоглазых и один кареглазый". Что из этого можно вытащить?

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

Воскресенье:
Вася видит, что Петя и Серёжа голубоглазые. Значит, посетитель соврал.
Но Петя и Серёжа видят цвет глаз друг друга и он голубой, тогда Вася знает, что Петя и Серёжа тоже знают, что посетитель соврал.
Тогда для всех троих истинным становится высказывание "на острове по крайней мере один голубоглазый".

(перемотаем на пару дней)

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

Ну и всё, в среду всем троим уже кирдык.

-- добавлено через 13 минут --

sergey zhukov в сообщении #1725155 писал(а):

А если изначално был один кареглазый, то что тогда? Тоже догадаются правильно?

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

[mihaild]

wrest
Если посетитель может врать, то все эти рассуждения не работают.

wrest в сообщении #1725174 писал(а):

Тогда для всех троих истинным становится высказывание "на острове по крайней мере один голубоглазый".

Не истинным, но известным для каждого. Оно таким и было.
Но всё еще Вася не знает, знает ли Петя, знает ли Сережа, что есть голубоглазые. И публичное бросание монетки ему никак это узнать не поможет.

wrest в сообщении #1725174 писал(а):

все живые, значит они все знают что все знают, что голубоглазых минимум два

С чего бы?

[wrest]

mihaild в сообщении #1725175 писал(а):

С чего бы?

C того, что с воскресенья на понедельник они не кирдыкнулись, а значит были не уверены в том, какого они цвета.

-- добавлено через 2 минуты --

mihaild в сообщении #1725175 писал(а):

Не истинным, но известным для каждого. Оно таким и было.

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

-- добавлено через 2 минуты --

mihaild в сообщении #1725175 писал(а):

Если посетитель может врать, то все эти рассуждения не работают.

В том то и фишка, что неважно говорит ли посетитель правду. Результат один - всем кирдык.

Далее - перевод.

Автор: Winkler, Peter
Название:  Mathematical mind-benders
Перевод названия: Математические закручки
ISBN: 9781568813363

стр. 95-97

-- добавлено через 25 минут --

Самоубийства в Городе Точек

Эта необычайно общая головоломка типа «знание о знании» пришла ко мне от Ника Рейнгольда из AT&T Labs. Различные более специфические версии (часто еще более дурного вкуса, чем эта) существуют уже много десятилетий.

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

Главный сюрприз здесь не только в том, что любое высказывание незнакомца становится катастрофическим; дело в том, что даже когда он говорит что-то, что, как все знают, является ложью, жители Города Точек обречены этим высказыванием. Мы докажем это ниже, но, возможно, будет убедительнее сначала рассмотреть небольшой частный случай и посмотреть, как это работает.

Предположим, что жителей всего трое, и у всех синие точки, а незнакомец говорит им: «Все точки красные». Все видят, что он лжет, но Житель 1 рассуждает так: «Предположим, что моя точка красная; тогда Житель 2 видит мою красную точку и задается вопросом, видит ли Житель 3 две красные точки. Если да, то, думает Житель 2, Житель 3 поверит незнакомцу и покончит с собой сегодня ночью, даже несмотря на то, что его точка синяя. Если он этого не сделает, Житель 2 правильно заключит, что Житель 3 увидел только одну красную точку, и покончит с собой на вторую ночь. Поскольку ни одно из этих событий не происходит, Житель 1 заключает, что Житель 2 не видел красной точки; следовательно, Житель 1 знает, что его точка синяя, и совершает самоубийство на третью ночь».

Чтобы доказать общий случай, нам понадобятся некоторые обозначения. Пусть $S \subset \{0, 1, \dots, n\}$ будет множеством чисел $x$ со свойством, что если среди $n$ жителей Города Точек имеется $x$ синих точек, то высказывание незнакомца истинно; наше предположение о нетривиальности говорит нам, что $S$ является собственным непустым подмножеством. Пусть $b$ будет фактическим количеством синих точек, которое может входить или не входить в $S$.

Для Жителя $i$ пусть $B_i$ будет множеством, состоящим из возможных количеств синих точек с точки зрения $i$. До визита незнакомца $B_i = \{b_i, b_i + 1\}$, где $b_i$ — это количество синих точек, которое $i$ видит у своих сограждан.

Если в какой-то момент $B_i$ сокращается до одного значения, Житель $i$ обречен. Это произойдет немедленно, если $|B_i \cap S| = 1$, но это также случится на ночь после любых самоубийств. Чтобы увидеть это, мы сначала заметим, что все жители с одинаковым цветом точек будут вести себя идентично, так как они все видят одинаковое количество точек. Таким образом, если Житель $i$ видит, что кто-то совершил самоубийство, он (правильно) заключает, что цвет точки этого человека отличается от его собственного; следовательно, он узнает свой собственный цвет и обречен.

Учитывая $S$ и $b$, пусть $d(b)$ будет числом шагов (увеличений или уменьшений на 1), необходимых для того, чтобы перейти от $b$ через границу $S$; другими словами, $d(b)$ — это наименьшее $k$, такое что $b + k$ или $b - k$ находится в $\{0, 1, \dots, n\}$, но в $S$ (если $b$ не в $S$) или вне $S$ (если $b$ в $S$).

Например, если $n = 10$ и $S = \{0, 1, 2, 9, 10\}$, то $d(0) = 3$, $d(1) = 2$, $d(2) = d(3) = 1$, $d(4) = 2$, $d(5) = d(6) = 3$, $d(7) = 2$ и $d(8) = d(9) = d(10) = 1$.

Мы уже отмечали, по сути, что если $d(b) = 1$, то самоубийства произойдут уже в первую ночь. Теперь мы утверждаем, что, более общо, первые самоубийства произойдут ровно в ночь $d(b)$.

Доказательство проводится индукцией по $d(b)$. Предположим, что это верно всякий раз, когда $d(b) < t$, и теперь пусть $d(b) = t > 1$. На день после ночи $t - 1$, так как самоубийств еще не произошло, все узнают, что $d(b) \ge t$. Однако, если $d(b) = t$, то либо $d(b - 1)$, либо $d(b + 1)$ должно быть равно $t - 1$. Если первое, то те жители с синими точками — которые видят, что количество синих точек либо $b$ (фактическое число), либо $b - 1$ — могут отбросить $b - 1$ и покончить с собой. Если второе, то это люди с красными точками, которые могут отбросить $b + 1$ и должны покончить с собой. Наконец, если $d(b - 1) = d(b + 1) = t - 1$, то никто не переживет эту ночь.

Поскольку $d(b)$ не больше $n$, доказательство говорит нам, что все погибнут к $n$-й ночи. Мы также можем видеть, что они продержатся так долго только в четырех крайних случаях: когда $b = 0$ и $S = \{n\}$ или $\{0, 1, \dots, n - 1\}$, и когда $b = n$ и $S = \{0\}$ или $\{1, 2, \dots, n\}$. Один из способов сказать это — время выживания максимизируется, когда незнакомец либо делает наименее информативное верное утверждение, либо говорит самую возмутительную ложь.

Возможно, стоит также отметить, что определение $d(b)$ не делает различия между $S$ и его дополнением; из этого следует, что не имеет значения, говорит ли незнакомец «$X$» или «Не $X$», жители Города Точек будут вести себя в обоих случаях абсолютно одинаково.

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

Хрупкий народец эти жители Города Точек. Как ни странно, однако, их хрупкость могла бы спасти их; Стив Бэббидж, менеджер и криптограф из Vodafone, указывает, что если они начнут беспокоиться, что самоубийство было вызвано не знанием цвета своей точки, а, возможно, тем, что какой-то житель Города Точек «наконец сломался под напряжением жизни в такой нелепой обстановке», — то при определенных обстоятельствах остальная часть города все же может пережить вторжение незнакомца.

[mihaild]

wrest в сообщении #1725191 писал(а):

Если да, то, думает Житель 2, Житель 3 поверит незнакомцу

Вот это непонятно откуда взялось.

[wrest]

mihaild в сообщении #1725204 писал(а):

Вот это непонятно откуда взялось.

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

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