Смешно, мне кажется, в этой задаче обычно говорят про чумазых девушек.
http://www.nes.ru/russian/about/MassMedia/BremzenSonin-Expert-17-10-05.htm

(Ответить) (Thread) (Expand)

Я читал это у Литлвуда в Математической смеси. Правда, там n=N

(Ответить) (Parent) (Thread)

замечательный вариант задачи. Спасибо.

(Ответить) (Thread)

согласен)) Читаю блог оригинале - забавно

(Ответить) (Parent) (Thread)

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

(Ответить) (Thread)

как-то оно по-анонимному вышло.

(Ответить) (Parent) (Thread) (Expand)

Это ж про математиков и их неверных жон!

(Ответить) (Thread)

принять ответ станет значительно легче, если представить двух друзей, голубоглазого и кареглазого, и понять, что между ними ЕСТЬ разница - один видит N голубоглазых, а другой - N-1.

(Ответить) (Thread)

действительно.
Спасибо за этот коммент, а то я голову сломала, пыаясь понять решение! Теперь гораздо яснее.

(Ответить) (Parent) (Thread)

Интересно - а как члены племени которые никогда и не с кем не обсуждают цвет глаз могут знать, что они сами либо голубоглазы либо кареглазы?

А вариант про убийство и правда похож на решение проблемы наименьшей кровью...

(Ответить) (Thread) (Expand)

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

Скорее, они сядут в круг и решат бросить жребий.

Кому выпадет, того и убьют, если он голубоглазый. А если он кареглазый, то его не убьют и он сам себя убьёт завтра, а сегодня он выберет себе любого голубоглазого и убьёт его.

(Ответить) (Parent) (Thread)

"В этом гипотетическом мире Б не знает, что В видит хотя бы одного голубоглазого!"

Подсказка путешественника несет новую мета-мета-информацию только в том случае, пока какой-нибудь житель может предположить, что хотя бы один человек может думать, что на острове нет голубоглазых. Если голубоглазых четверо, то в воображении А, придумывающего логику дла Б, придумывающего логику дла В, придумывающего логику дла Г, последний в цепочке Г обязательно должен увидеть голубые глаза Б. Тогда сразу начнется отсчет дней до общего самоубийства.

(Ответить) (Thread)

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

Зато он может предположить, что другой предположил, что (...) у него голубые глаза.

Если голубоглазых четверо, то в воображении А, придумывающего логику дла Б, придумывающего логику дла В, придумывающего логику дла Г, последний в цепочке Г обязательно должен увидеть голубые глаза Б.

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

(Ответить) (Parent) (Thread) (Expand)

Не надо никого убивать. Ну соврал человек, с кем не бывает...

---

Так. А как это preview получился отдельным постингом, да ещё и незалогиненным?

Edited at 2008-02-13 05:44 (UTC)

(Ответить) (Thread)

Все-таки не до конца понятно. Островитянам думать-то не запрещено, а только обсуждать? Почему же все голубоглазые не убьются на 100-й день без всякого путешественника? Ведь если житель острова, видящий перед собой 99 голубоглазых, задастся вопросом "какого цвета моии глаза", он получит для себя ответ на сотый день. При условии, конечно, что и остальные островитяне так же любопытны в отношении себя, но это вроде как подразумевается, раз за узнавание цвета глаз положено такое строгое самонаказание.

(Ответить) (Thread) (Expand)

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

(Ответить) (Parent) (Thread) (Expand)

Слушай, а почему на 100-й день с собой покончит именно сотня голубоглазых аборигенов? Почему одновременно с ними не придут кончать с собой 900 кареглазых, точно так же и на тех же основаниях решив, что они голубоглазы?

Вопрос могу развить, но если ты ответишь мне на этот, думаю, дальше смогу сам допетрить.

(Ответить) (Thread) (Expand)

Потому что кареглазые аборигены видят не 99 голубоглазых аборигенов а 100. То есть следуя этой логике они будут с собой кончать на 101-ый день

(Ответить) (Parent) (Thread) (Expand)

Вспомнился рассказ Азиза Несина, как одна политическая партия (скажем, ЕР) решила погубить другую (скажем, СР), пригласив всех на митинг примирения в цирк шапито. Каждый член ЕР принес с собой дубинку и по сигналу (шест подрубают, шатер накрывает всех) должен был отдубасть соседнего СРовца.
Угадай, чем кончилось? :)

Названия не помню, в сети найти не смог.

(Ответить) (Thread)

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

А как может быть иначе, если каждый видит как минимум 99 голубоглазых? Каким образом при этом можно не знать о том, что каждый это видит? Т.е. если я житель этого острова, то я знаю, что любой из моих сограждан видит либо 100, либо 99 голубоглазых, и соответственно, знает о том, что голубоглазые существуют.

(Ответить) (Thread) (Expand)

Ну ведь Толя же с этого начал:
"С одной стороны, путешественник не сообщил островитянам никакой новой информации. Он сказал им, что среди них есть хотя бы один голубоглазый житель; но каждый из них и так это знал, потому что видел вокруг себя кто 99, кто 100 голубоглазых жителей."

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

(Ответить) (Parent) (Thread) (Expand)

Что произойдёт в случае родов в промежутке между объявлением путешественника и наступлением дня N?

(Ответить) (Thread) (Expand)

Все напьются.

(Ответить) (Parent) (Thread) (Expand)

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

(Ответить) (Thread)

"Бороду-то я могу сбрить, а вот умище-то куда девать"

(Ответить) (Parent) (Thread)

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

Эта интерпретация не может быть верной :) Все поголовно знали что есть голубоглазые и до этого. Про мета-информацию где-то ближе к телу. Речь все же о 'знают что другие знают ...'

(Ответить) (Thread)

Есть такой термин "общее знание".

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

(Ответить) (Parent) (Thread) (Expand)

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

Ещё проще, конечно, это попросить болтливого иностранца показать на одного конкретного голубоглазого.

(Ответить) (Thread)

вообще, мне кажется, что смерть одного голубоглазого (ГГ) ситуации не изменит (тем более, что все одновременно придут к этому выводу и перебьют всех ГГ, если это будет решением проблемы). ведь в случае, если их станет меньше на одного, логика останется прежней, но уже для 99 ГГ, которые покончат с собой на 99-й день. А вот если день на 95-й придёт этот путешественник и замочит штук 6 ГГ, то это собъёт индукцию. 94-й день, на который оставшиеся должны были бы умереть, уже прошёл, а из новой информации такой логики уже не вытекает - если он убил всех ГГ, никто из оставшихся достоверно об этом не узнает - вдруг он оставил одного? Осталось столько, сколько он захотел оставить.

(Ответить) (Parent) (Thread) (Expand)

Секунду, если распространить логику с трех жителей на всех. Каждый из них думает - если сегодня никто из голубоглазых (он их видит, их 100 человек) не убил себя, значит голубоглазый я. Таким образом на второй день племя должно совершить массовое самоубийство.

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

(Ответить) (Thread) (Expand)

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

(Ответить) (Parent) (Thread)

malfet_ дело говорит. 5x6веник должен ещё сказать, что остальные кареглазы. А то вдруг я зеленоглазый?

(Ответить) (Thread)

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

(Ответить) (Parent) (Thread) (Expand)

Ха-ха, смешная задачка. Тут есть подвох в ее изложении. Именно поэтому люди и тупят. На самом деле, чужестранец сообщил им дополинтельную информацию. Потому что на острове может не быть вообще голубоглазых людей. В частности поэтому, единственный голубоглазый, который видит только кареглазых не может точно знать цвет своих глаза, он может быть, как голубоглазым, так и кареглазым. А это базис индукции для доказательства того факта, что общество находится в стабильном состоянии!

(Ответить) (Thread)

Да, но в условии - 100 голубоглазых (а не >= 1), соответственно по крайней мере 99 из nih каждый видел до этого. То есть не мог подумать что их нет вообще.

(Ответить) (Parent) (Thread) (Expand)

This highlights the stabilizing influence of fools on your society. Just to have one about which the others can not be certain if he has mastered math induction ....

(Ответить) (Thread) (Expand)

Именно поэтому другой вариант задачки - про математиков и их неверных жён, а не про варваров :)

(Ответить) (Parent) (Thread)

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

(Ответить) (Thread) (Expand)

Рассмотрим варианты:
1. Голубоглазый житель только один. Тогда, из слов иностранца он узнает свой цвет глаз (так как он видит, что остальные кареглазые) и на следующий день совершает самоубийство.
Так как, на следующий день после заявления иностранца только один житель совершил самоубийство, то все остальные жители понимают, что они кареглазые и на второй день совершают массовое самоубийство.
2. Голубоглазых жителей двое. Например, житель «А» и житель «B». «А» видит «В», а «В» видит «А», также оба видят, что остальные жители кареглазые.
Ситуация со стороны «А» выглядит так: 998 – кареглазые, 1 – голубоглазый и 1 (сам «A») -неизвестен. Т.е. максимально возможное число голубоглазых = 2.
Ситуация со стороны кареглазого жителя: 997 – кареглазые, 2 – голубоглазые и 1 – неизвестен. Т.е. максимально возможное число голубоглазых = 3.
- на следующий день, голубоглазый «B» не совершает самоубийства, хотя это ожидает «А».
в этот момент «А» понимает, что «В» не совершает самоубийство, так как ожидает этого шага именно от «A». Тогда «А» понимает, что он голубоглазый.
- такая же логика касается и «В»: видя, что «А» не совершает самоубийство, он тоже понимает, что он голубоглазый.
- на второй день они оба совершают самоубийство.
- после двойного самоубийства «A» и «B», остальные понимают, что голубоглазых больше нет: так как только, если их было двое, то они оба совершат самоубийство на второй день.
И значит, все кто остался – кареглазые, в том числе и ты сам.
- на третий день все остальные (998) жителей совершают массовое самоубийство.

3. Голубоглазых жителей трое. Например, житель «А», житель «B» житель «С». «А» видит «В»и «С», «В» видит «А» и «С», «С» видит «B» и «С», также видят, что остальные жители кареглазые.
Ситуация со стороны «А» выглядит так: 997 – кареглазые, 2 – голубоглазый и 1 (сам «A») -неизвестен. Т.е. максимально возможное число голубоглазых = 3.
Ситуация со стороны кареглазого жителя: 996 – кареглазые, 3 – голубоглазые и 1 – неизвестен. Т.е. максимально возможное число голубоглазых = 4.

- житель «А» видит, что в первый день никто не совершил самоубийство (такой вариант возможен только, если голубоглазый только один, а «А» видит уже двоих).
- на второй день самоубийства тоже не происходит (такой вариант возможен только, если голубоглазых двое). В этот момент «А» понимает, что он голубоглазых больше 2, но так как он знает, что их не больше 3, то голубоглазый именно он.
- такая же логика касается «В» и «С»: они понимают, что они голубоглазые.
- на третий день «А», «В» и «С» совершают самоубийство. Остальные понимают, что голубоглазых больше нет.
- на четвертый день все остальные (997) жителей совершают массовое самоубийство.
И так далее. При увеличении доли голубоглазых в общем числе, растет количество дней в течении которого голубоглазые узнают собственный цвет глаз. Для 100 голубоглазых – это 100 дней. После того как на 100 день все голубоглазые совершат самоубийство, то остальные поймут, что они кареглазые и совершат самоубийство на 101 день.
Итог: племя прекратит свое существование на 101 день.

(Ответить) (Parent) (Thread)

-- Всего на острове живет 1000 человек, из них 100 голубоглазых и 900 кареглазых

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

(Ответить) (Thread) (Expand)

Они знают распределение с точностью до одного. Одни думают, что голубоглазых 100 или 101, другие что 99 или 100

(Ответить) (Parent) (Thread) (Expand)

взять всех и замочить

(Ответить) (Thread)

Глаза выколоть и не жить долго и счастливо;)

(Ответить) (Parent) (Thread)

Но поскольку среди голубоглазых полная симметрия, не должны ли они убиться в один день вместе, или никогда ?

(Ответить) (Thread) (Expand)

"правильное решение действительно состоит в том, что все голубоглазые убьют себя на 100-й день. "

(Ответить) (Parent) (Thread) (Expand)

Продумал загадку, не дочитав до конца пост. Также пришел к выводу о необходимости срочного убийства какого-нибудь голубоглазого.
Подумал еще, и решил, что такой ответ неверен. По двум причинам.
Во-первых, в условиях задачи подразумевается (хоть явно и не прописано, что не есть хорошо) исключительно высокоразвитое логическое мышление всех аборигенов. Соответственно, светлая мысль об убийстве одного голубоглазого придет в головы почти всем аборигенам - и чужестранца ждет незабываемое зрелище массовой резни.
Во-вторых (и это главное) даже если найдется только один такой умник, то ситуация принципиально не измениться - на острове останется 99 голубоглазых, ВСЕ аборигены будут знать, что есть хотя бы один (точнее, хотя бы 98) голубоглазых, точка отсчета будет продолжать существовать. Следовательно, единственное, чего доброхот добьется - приближения апокалипсиса на 1 день.
Так что, верный ответ остается старым: самоубийство голубоглазых на 100-й день и кареглазых на 101-й. Конечно, при условии, что все аборигены, сцуко, умные! :)

(Ответить) (Thread) (Expand)

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

(Ответить) (Parent) (Thread)