На далеком-далеком острове жили два типа людей: голубоглазые и черноглазые. Стоит заметить, что все они были идеально умные. Также жители острова не могли передавать кому-либо какую-то информацию(то есть они были немые, не умели общаться на языке жестов и т.д.) Существовало у туземцев такое правило: если житель острова узнает цвет своих глаз, он идет к высокому обрыву, прыгает оттуда и разбивается насмерть. Сброситься со скалы туземец может каждый день ровно в 17-00. Для того, чтобы узнать свой цвет глаз, туземец не может смотреть в воду, зеркало и т.д.
Всё у жителей острова было хорошо до тех пор, пока к ним не приехал иностранец. Он пожил на острове несколько месяцев. И вот, настало время ему уезжать. Иностранец сел в лодку, и перед тем, как отправиться в далекий путь, сказал лишь одну фразу:"Как здорово, что я увидел человека, такого же голубоглазого, как я". Лодка иностранца тут же покинула пределы острова. Опишите, что произошло на острове после отъезда иностранца.
З.Ы. Правильное решение задачи я пока-что не придумал.
З.З.Ы Огромное спасибо пользователю SkidanovAlex за корректировку условия и детальный разбор задачи.
почему - надо еще подумать...
пусть голубоглазый видит k других голубоглазых. если их 0 - он прыгает. иначе он может рассуждать так: "предположим, что я черноглазый. тогда любой из других голубоглазых видит k-1 голубоглазых и может ТАК ЖЕ КАК Я предположить, что он черноглазый и посчитать, что голубоглазых k-2, каждый из которых ТАК ЖЕ КАК ОН может предположить, что он черноглазый и посчитать, что голубоглазых k-3 и т.д., последний видит 0 и прыгает. однако все живы - противоречие. значит я голубоглазый" - и прыгает.
итак, у нас есть более менее строгое доказательство, что один голубоглазый точно спрыгнет. кстати, черноглазому тоже ничего не мешает так рассуждать и ошибочно предположить что он голубоглазый если все голубоглазые тормоза хД. но, думаю, что это таки не так. когда один товарищ уже спрыгнет - вышеописанные рассуждения уже не катят.
и все таки, иностранец сказал что видел хотя бы 1 или 2х голубоглазых? плюс к этому - можно ли полагать, что каждый знает цвета глаз всех остальных, их самочувствие? кроме того - как быть с туземцами-тормозами (думает идеально, но мееедленно)?
1)"Как хорошо, что на вашем острове я наконец-то увидел голубоглазых!" - их минимум 2.
2)Каждый знает цвет глаз каждого
3)"Тормозов" там, насколько я понял условие, нет. Зато есть люди, которые оценивают поведение других и делаю соответствующие выводы.
кстати ;)
Мы эту задачу на максимум сдали, исключительно подбором)))
Как правильно решается - забыл.
Там вроде бы если зеленоглазых больше 0 то 2 дня, а иначе 1 день. Хотя не логично как-то)))
Мне кажется, что если темно-синеглазых больше 1 то деревня не должна опустеть, тогда надо вывести 0.... но по условию то надо вывести натуральное число, и "деревня опустела..."... так что хз)))
Проблема некоторых людей в том, что они доказывают неверно:
"Пусть на острове было 100 голубоглазых. Турист, сказав, что на острове есть голубоглазые не дал никакой новой информации, и ничего не изменится". Это не верно, турист дал новую информацию.
Сначала рассмотрим нормальное условие, нормальное решение, а потом поймем, какую же информацию дал турист.
Во-первых, в настоящем условии турист сказал "как здорово, что я увидел человека, такого же голубоглазого как я", и в этом была конкретная информация: на острове есть хотя бы ОДИН голубоглазый. Но если он сказал про двух, ничего не меняется - просто все сдохнут на день раньше.
Второе обязательное условие: они прыгают один раз в день ровно в 17:00 (или любое фиксированное время) и если прыжок туземца дал информацию другому туземцу, он прыгнет только на следующий день.
Третье обязательное условие: у туземцев нет случайного способа узнать цвет глаз (посмотреть в воду, прозреть).
Ну и наконец, туземцы идеально умны и могут сделать любое умозаключение, даже если оно требует рекурсии глубины 100 (а оно требует :о)).
Дальше доказательство по индукции. Мы рассмотрим вариант когда на острове один голубоглазый, когда два, и когда N (достаточно было бы рассмотреть только одного и N, но без двух не очень понятно).
Итак, пусть голубоглазый один. Турист говорит "как я рад, что на острове есть голубоглазый". Голубоглазый смотрит по сторонам, и видит, что голубоглазых нет. Он все понимает и в 17:00 он убивается об скалы. В этот момент все остальные туземцы понимают, что раз он убился, а голубоглазых вокруг нет, то значит они - кареглазые, и на следующий день в 17:00 херачатся об скалы.
Теперь можно было бы перейти к шагу индукйции, но сначала для его понимания рассмотрим вариант с двумя туземцами с голубыми глазами. Итак, турист уехал, каждый из двух ту смотрит по сторонам и видит, что есть вокруг один голубоглазый туземец. Значит, турист мог говорить о нем. Проходит день, и никто не сбросился. Какой вывод делает каждый голубоглазый туземец? Если бы тот голубоглазый туземец, которого я видел, был единственным, он бы сбросился, но он этого не сделал. Значит, голубоглазых хотя бы два, и так как я вижу одного - я второй. В 17:00 второго дня оба голубоглазых прыгают об скалы. На третий день все кареглазые понимают что к чему и прыгают за ними.
Теперь шаг индукции. Для N-1 уже доказано, что если голубоглазых N-1, то они все убьются на N-1 день, а на N-ый день убьются все кареглазые. Теперь пусть голубоглазых N. В первые N-2 дня очевидно ничего не произойдет. На N-1 все голубоглазые смотрят друг на друга с затаившимся дыханием, но никто не прыгает! Все голубоглазые, видя вокруг себя всего N-1 голубоглазого, понимают, что на острове НЕ N-1 голубоглазый (иначе бы все голубоглазые убились), а значит каждый из них со своей точки зрения понимает, что он, тоже голубоглазый, и на следующий день он убивается. То есть все голубоглазые убьются на N-ный день. Кареглазые на N+1. Что итд.
Теперь, вопрошающий взгляд: "это все понятно, но странно, ведь мы с самого начала поняли, что турист не сообщил новой информации". Вот это не правда.
Давайте подумаем, если Г один, какую информацию сообщил турист? Очевидно - что на острове вообще есть Г. Почему Г не убивался раньше? Потому что он не знал, есть ли на острове хотя бы один Г, а теперь знает. И убивается. То есть, когда Г один, информация = "на острове есть хотя бы один Г"
Тепреь, когда Г два, почему они не убиваются? Каждый из них видит одного Г, но он не знает, знает ли этот Г, что на острове вообще есть Г. То есть тот Г, которого мы видим, может быть единственным Г, но не убиваться, потому что он не знает, есть ли на острове вообще Г. Турист сообщает, что на острове есть Г, и тепеть мы знаем, что все на острове знают, что на острове есть Г. А значит туземец Г которого мы видим это знает, и если он не убился, то значит я тоже Г.
Рассмотрим пример для трех подробно. Каждый раз смотрим со стороны одного Г. Понятно, что все Г мыслят одинаково.
До туриста:
1. Я вижу перед собой два Г
2. Как сейчас мыслит один из этих двух Г? Это зависит от того, что он видит.
2.1. Если я - Г, то он видит двух Г, мыслит как я, и поступит как я.
2.2. Если я - К, то он видит одного Г, тогда он думает "я вижу перед собой одного Г ..."
2.3. " ... а как сейчас мыслит этот один Г? ..."
2.4.1. ".. если я - Г, то он видит одного Г, мыслит как я и поступит как я .."
2.4.2. "... а если я - К, то он не видит ни одного Г, но он не знает, если на острове хотя бы один Г, и ему все пофигу ..."
2.5. "... тогда и мне все пофигу ..."
3. тогда и мне все пофигу
После туриста:
1. Я вижу перед собой два Г
2. Как сейчас мыслит один из этих двух Г? Это зависит от того, что он видит.
2.1. Если я - Г, то он видит двух Г, мыслит как я, и поступит как я.
2.2. Если я - К, то он видит одного Г, тогда он думает "я вижу перед собой одного Г ..."
2.3. " ... а как сейчас мыслит этот один Г? ..."
2.4.1. ".. если я - Г, то он видит одного Г, мыслит как я и поступит как я .."
2.4.2. "... а если я - К, то он не видит ни одного Г, но он ЗНАЕТ, что на острове хотя бы один Г, и он убьется на первый день..."
2.5. "... но если он не убился, то я тоже Г, и я убьюсь на второй день. и он тоже, он мыслит как я ..."
3. но если они не убились на второй день, значит что и я Г, и я убьюсь на третий день. Как и они - они мыслят и поступают как я.
Я строил на одном форуме (где были безнадежно тупые люди, которые не понимали этого доказателсьтва) такую же выкладку для пяти человек. Это не важно на самом деле сколько человек, турист действительно сообщает новую информацию, даже если на острове миллион голубоглазых. Грубо говоря, если на острове 3 человека, то
1. Все знают, что на острове есть голубоглазый
2. Все знают, что все знают, что на острове есть голубоглазый
3. НО! Не все знают, что все знают, что все знают, что на острове есть голубоглазый.
Когда же турист сказал, что он есть. то теперь утверждение
(Все знают, что)* что на острове есть голубоглазый
Любой длины верно, и именно в этом заключается новая информация.
если голубоглазых 1, то вывести 1
если голубоглазых больше 1, то вывести 3
N + ((K==0)?0:1)
Все голубоглазые убьются на N-ый день, кареглазые на следующий. Если карезгалых нет, ответ N, иначе N+1
Непонятен пункт 2.4.1:
2.4.1. ".. если я - Г, то он видит одного Г, мыслит как я и поступит как я .."
Почему он видит одного Г? Он видит "меня" и Г, описаного в пунктах 2.1-2.2.
2.4.1 заключается в следующем: Первый думает "если я К, а второй думает, что он Г, то что, по мнению второго, думает третий. Третий, по мнению второго, думает - я вижу одного Г, ... ...".