Остров невезения
Беда-беда… Задачке про остров правдословов явно не повезло: её так никто и не решил. Видать, слишком сложную задачку я вам на этот раз загадал. Из тех, кто вслед за Теннисоном боролся и искал, но сдался не найдя, хочется отметить
Дикую кошшшку, которая заслуженно получает приз за волю к победе :)
Ладно. А теперь по существу:
Хитрость задачи. В чем же тут секрет? Ведь речь Гуру не содержала в себе ничего нового. Все присутствующие на острове и так знали, что среди них есть голубоглазые. Что же изменилось после его слов? Для того, чтобы понять это, давайте представим, что на острове всего два голубоглазых. Каждый из них видит глаза другого и знает, что, действительно, на острове есть голубоглазые. Но (и тут надо поставить три восклицательных знака) после слов Гуру они будут знать, что все знают о том, что на острове есть голубоглазые. И это будет для них новой информацией. Действительно, ведь каждый из голубоглазых (не зная цвет своих глаз) может рассуждать так: допустим у меня карие глаза. Тогда этот бедняга (другой голубоглазый) единственный островитянин с голубыми глазами. И, разумеется, тогда он не знает, что на острове есть голубоглазые. А теперь, после слов Гуру, он будет об этом знать.
Уловили логику рассуждений? В случае, когда на острове есть только три голубоглазых, до речи Гуру каждый знает, что на острове есть голубоглазые, и более того, каждый знает, что все знают о том, что на острове есть голубоглазые. А после речи Гуру к этому перечню добавляется новая информация; в частности, теперь каждый знает, что каждый знает, о том что все знают, что на острове есть голубоглазые :). Хитро? Хитро. Но, раз вы ленились решать задачу, то не поленитесь поразмыслить над этим рассуждением. Ну как, почувствовали, что в публичном выступлении Гуру был смысл, что оно само по себе несло новую информацию?
Вообще говоря, в нашей задаче после речи Гуру все островитяне узнают, что все знают о том, что все знают о том, что все знают о том, что… [и так до бесконечности]…, что на острове есть голубоглазые. До выступления Гуру этой “бесконечной” вложенности утверждений не было; все ограничивалось лишь 99 вложениями.
Вот и вся хитрость :)
Решение задачи. Собственно, если вы поняли приведенные выше рассуждения, то сможете с их помощью решить эту задачу. Ну? У вас есть последний шанс! Кхм. Ладно… Итак, рассказываю решение.
Для простоты представим, что на острове есть лишь один голубоглазый. Тогда задача тривиальна: услышав слова Гуру наш голубоглазый понимает, что речь идет о нем (ведь других голубоглазых на острове нет - глаза всех остальных островитян он видит). Поэтому грядущей ночью он сядет на корабль и покинет этот бренный остров.
Хорошо. Пусть теперь на острове будет два голубоглазых. После слов Гуру они оба (впрочем, как и все остальные жители острова) задумаются: а голубые ли у меня глаза, или нет? Не найдя ответ на этот вопрос они пойдут спать. Проснувшись они обнаружат, что ночью никто не уплыл с острова. «Ага», скажет себе каждый из голубоглазых, «будь у меня не голубые глаза этот бы второй догадался, что он голубоглаз и отчалил бы минувшей ночью. Но это не уплыл. Значит у меня голубые глаза». И на вторую ночь эта парочка покинет остров.
Думаю, вы уже поняли, что произойдет, если на острове будет три голубоглазых жителя. После речи Гуру каждый из них скажет себе: «Допустим, что я не голубоглаз. Тогда на острове всего два голубоглазых жителя. Но этот случай тривиален - смотри предыдущий абзац. Что же, подождем пару дней». Проходит две ночи, но никто не уплывает с острова. И каждый из голубоглазых понимает, что изначальное предположение было неверным. И каждый из них осознает, что у него голубые глаза. И на третью ночь они дружно уплывают с острова.
Ну, и так далее :). В нашей задаче, сотня голубоглазых героев сделает аналогичное предположение, прождет 99 дней и постигнув цвет своих глаз на 100-ю ночь покинет остров. Ура :) А что же будет с другими островитянами?
А ничего. Каждый из кареглазых задаст себе тот же вопрос: голубые ли у них глаза? Но каждый из кареглазых видит перед собой 100 голубоглазых, поэтому они будут выжидать 100 дней - и они дождутся того, что все голубоглазые покинут остров. И тогда каждый из кареглазых поймет, что у него не голубые глаза. (Будь у него голубые глаза, вся ватага голубоглазых сидела бы на острове еще один день.) Но это, увы не позволит кареглазым понять истинный цвет своих глаз. Да, они не голубоглазы, но мало ли какого цвета у них глаза? Серые? Бурые? Малиновые? :) Так что кареглазым и умудренному Гуру придется остаться на острове…
Ответ: Через 99 дней (на 100-ю ночь) все голубоглазые покинут остров. Все остальные жители будут ждать следующего откровения Гуру.
Глубокий философский смысл. Эта задача является прекрасной иллюстрацией к теории информации. Кроме того, в ней таится глубокий философский смысл. Невольно на ум приходит примерно такая аналогия: вроде бы все понимают, что в стране бардак (все воруют, кругом сплошные откаты, понаехали тут и проч. - нужное подчеркнуть), но если об этом не говорить вслух, то ничего не изменится…