Помогите разобраться с парадоксом (голубоглазые островитяне)

[мат-ламер]

Задача (взял с http://terrytao.wordpress.com/2008/02/05/the-blue-eyed-islanders-puzzle/). На неком острове жувут аборигены - 100 голубоглазых и 900 кареглазых (другие цвета глаз исключаются). На острове странная религия. Жителям запрещается обсуждать тему о цвете глаз и сообщать кому-либо, какого цвета у того глаза. Так что никто не знает - какого цвета у него глаза (зеркал на острове нет). Хотя какого цвета глаза у других - осведомлён хорошо. Более того, если кто-то узнает (или догадается), какого цвета у него глаза, он должен на следующий день на виду у всех совершить ритуальное самоубийство. Жители на острове все умные и религиозные. И каждый знает об этом. Случайно на остров приезжает путешественник и, так и не разобравшись в обычаях туземцев, перед отъездом бросает неосторожную фразу - "Странно было встретить на Вашем острове человека с такими же голубыми глазами, как у меня". Вопрос - к чему может привести такая случайно оброненая фраза? У меня сразу возникло два ответа. Первый. Ничего. Ведь путешественник не сообщил островитянам никакой дополнительной информации. И так все знают, что на острове есть голубоглазые. Второй. После некоторого периода осмысления информации, полученной от путешественика, дело может кончится массовым суицидом. Сначала голубоглазых, а затем и кареглазых. Мои ответы совпали с авторскими. Единственная трудность. Автор не сообщает, какой из двух ответов правильный и предлагает подумать об этом на досуге. Помогите разобраться.

[clerkx]

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

[мат-ламер]

Спасибо за ссылку. Я пока склоняюсь к первому варианту. Во втором варианте (массовый суицид) индукция не работает (ИМХО). Потому, что она начинается словами - допустим на острове один голубоглазый. Любому туземцу ясно, что на острове либо $99$ либо $100$ голубоглазых. Всего два варианта. Причём тут индукция?

[serval]

Цитата:

"Странно было встретить на Вашем острове человека с такими же голубыми глазами, как у меня"

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

[clerkx]

мат-ламер в сообщении #449357 писал(а):

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

Я склоняюсь ко второму :) Ведь вряд ли ответ на задачу зависит от количества жителей или от их пропорции. Т.е. если бы в условии было 2 голубоглазых и те же 900 кареглазых, то можно было бы и без индукции прийти к ответу о суициде.
Типа этого:

(Оффтоп)

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

Аналогичные рассуждения для 3-х:

(Оффтоп)

Г1 видит кареглазых, а так же Г2 и Г3. Он предполагает, если на острове есть только Г2 и Г3, то развернется описанная выше ситуация для 2-х голубоглазых и каждый из них на через день поймет, что их двое и убьется. Однако, если этого не происходит, значит и Г2 и Г3 каждый видели 2-х голубоглазых и (Г1 и Г2, например) и ожидали самоубийства со стороны двух других. Каждый из голубоглазых это понимает и убивает себя на 3-й день.

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

[Профессор Снэйп]

О, один из любимых парадоксов!!! Хотя про "повешенного" больше нравится.

На форуме НГУ разжёвано дальше некуда. См. здесь (вся тема с начала), после долгих непоняток и затупов объяснение было найдено в этом сообщении.

[hurtsy]

мат-ламер в сообщении #449357 писал(а):

Любому туземцу ясно, что на острове либо $99$ либо $100$ голубоглазых. Всего два варианта. Причём тут индукция?

serval в сообщении #449359 писал(а):

то голубоглазый легко вычислит себя, и после его самоубийства - все кареглазые тоже

Из процитированного следует, что островитяне не умеют считать до 100. Интересно, успеет ли миссионер развить у туземцев желание решать БТФ? С уважением,

[Circiter]

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

[Профессор Снэйп]

Ага. "Я знаю, что ты знаешь, что я знаю, что ты знаешь..." Есть ещё "У попа была собака", пример дурной рекурсии, оканчивающейся переполнением стека

[gris]

Как же хорошо не жить на таком острове и не ломать голову, должен ли ты убить себя, если случайно совершил мыслепреступление. Ведь именно таковое и предполагается в условиях. Отсюда вывод — быть умным и религиозным — мука ацкая и с жизнью не совместимая.
Да здравстует свобода (см. в соседней теме)!

[epros]

В варианте с двумя голубоглазыми - Вовой и Димой:

Изначально Вова НЕ ЗНАЕТ, знает ли Дима, что среди них есть голубоглазый.
Замечательно, бяка путешественник сказал им, что среди них есть голубоглазый.
Теперь Вова ЗНАЕТ, что Дима знает, что среди них есть голубоглазый. Он думает: "Это либо я, либо Дима ДУМАЕТ, что это он. Во втором случае он должен покончить самоубийством. Если не покончит, значит голубоглазый - я, т.е. покончить самоубийством должен я. Подождём, посмотрим".

Очевидно, Дима думает симметричным образом: Он тоже смотрит на Вову и ждёт, не покончит ли тот самоубийством.

Так они будут смотреть друг на друга и ждать до скончания веков.

[serval]

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

[clerkx]

epros в сообщении #449570 писал(а):

Очевидно, Дима думает симметричным образом: Он тоже смотрит на Вову и ждёт, не покончит ли тот самоубийством.

Так они будут смотреть друг на друга и ждать до скончания веков.

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

serval в сообщении #449583 писал(а):

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

Да, похоже так и будет :)

[epros]

clerkx в сообщении #449618 писал(а):

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

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

Вот смотрите: Вова видит, что Дима не собирается кончать с собой, и думает: "Всё, кранты. Ясен пень, что я - голубоглаз". Хватает ритуальный кинжал, замахивается... И тут он видит, что Дима синхронно с ним схватил ритуальный кинжал и замахнулся. "Как же так? А может я вовсе и не голубоглаз, ошибочка вышла?" И коллективное самоубийство откладывается до следующего цикла наблюдений и размышлений.

[clerkx]

epros в сообщении #449626 писал(а):

"Как же так? А может я вовсе и не голубоглаз, ошибочка вышла?"

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