или непонятно зачем,
или непонятно как.
Продолжим разбираться со вчерашней задачкой об острове без зеркал. Сначала коротко и сухо вспомним условие:
1. На острове 888 кареглазых и 111 голубоглазых сектантов. Они легко могут видеть друг друга и знают, что людей с другим цветом глаз на острове не может быть. Но каждый из них не знает цвет своих глаз.
2. Все островитяне очень умные, поэтому они догадаются до всего, до чего только можно догадаться. По этой причине они изначально не знают количество голубоглазых и кареглазых на острове (иначе бы они мгновенно вычислили свой цвет глаз).
3. Житель острова, узнавший цвет своих глаз, дожидается ближайшего парома (которые приходят в 17 часов каждый день), чтобы уехать навсегда.
4. Однажды на остров приезжает турист, чтобы пообщаться со всеми островитянами и насладиться красотой острова. Вопреки всем запретам на обсуждения цвета глаз, он во всеуслышание сообщает истинное утверждение, что среди островитян есть хотя бы один голубоглазый.
Вопрос: как поменяется жизнь на острове после отъезда разговорчивого туриста?
Сейчас я должен остановиться на минутку, чтобы предупредить: ниже будут предложены два «очевидно правильных» решения. Я думаю, что гораздо интереснее придумать их самостоятельно. Тогда потом будет дополнительный стимул, чтобы найти «виноватого» :)
Если вы уверены, что уже достаточно подумали, то приступим к разбору:
Первое решение:
Каждый житель острова видел 110 или 111 голубоглазых. Это означает, что каждый сектант знал, что на острове есть хотя бы один голубоглазый. Поэтому слова туриста ничего не меняют - островитяне как жили на острове раньше, так и дальше будут жить.
Второе решение:
Давайте решим эту задачу методом математической индукции. База индукции простая - пусть на острове есть один голубоглазый и много кареглазых сектантов. Получив подсказку от туриста, голубоглазый всё понимает: раз он видит вокруг только кареглазых, а хотя бы один голубоглазый на острове есть, то это именно он. Поэтому он - единственный голубоглазый - уплывёт с острова на первом же пароме.
Кстати, давайте поймём, что будет на следующий день: все кареглазые заметили, что голубоглазый, услышав слова туриста, неожиданно сорвался и уехал. Это означает, что голубоглазый не увидел вокруг себя других голубоглазых. Так все оставшиеся жители острова понимают, что они все кареглазые. Вывод - на второй день они тоже уплывут на пароме. И остров опустеет.
Что же, с базой индукции мы разобрались. Давайте сделаем шаг. Сразу предупрежу, что рассуждение будет достаточно абстрактным, поэтому предлагаю сначала понять более простую ситуацию (первый шаг).
Пусть на острове есть двое голубоглазых и много кареглазых. Как только турист сделал своё заявление, каждый голубоглазый думает: «Я вижу ровно одного голубоглазого. Если он уплывёт сегодня на пароме, значит я кареглазый. А если не уедет, значит он видит другого голубоглазого - меня. Поэтому мне придётся уехать завтра». Другими словами, завтра ему уезжать придётся в любом случае.
Теперь сделаем этот шаг строго. Предположение индукции: если на острове есть N голубоглазых и больше N кареглазых сектантов, то на N-ный день все голубоглазые уедут. А все кареглазые уедут на N+1-ый день
Доказательство: пусть на острове находятся N+1 голубоглазых и больше N+1 кареглазых.
Тогда каждый голубоглазый видит ровно N голубоглазых. И он понимает, что если цвет его глаз не голубой, то они все уедут на N-ный день (по предположению индукции). А раз они на N-ный день не уезжают, то это означает, что у него голубые глаза. Поэтому он должен будет уплыть на N+1-ый день.
Чувствуете проблему? У нас есть два вроде бы правильных решения, приводящих к противоположным ответам. Можно ли теперь пользоваться математической логикой? ;)
Но я уверен, с этим мы скоро окончательно разберёмся в комментариях. Кстати, заранее предупрежу, что в обсуждении предыдущей заметки есть очень точные замечания, поэтому я не рекомендую их читать, если есть желание понять тонкость своими силами. Это того стоит!
А если вы ещё не знаете, что все лошади на планете имеют лиловый цвет, то, возможно, будет полезно разобраться с «доказательством этого факта» - оно является в каком-то смысле базовым для понимания задачи о туристах на острове. Я имею в виду, что есть смысл заранее знать о некоторых ловушках, в которые можно попасть, пользуясь методом математической индукции :)
Хорошего вам окончания недели!
RSS-feed
А учитывая, что все островитяне у нас такие умные и быстро соображающие, как только американец сказал эти свои слова, все островитяне быстро правильно решают в уме эту задачу, сплёвывают себе под ноги, негромко матерятся, и идут собирать вещи, припоминая, сколько голубоглазых соседей они знают.
ОтветитьУдалитьПервое решение является правильным.
ОтветитьУдалитьВ решении с помощью индукции не учтены информационные аспекты. В шаге индукции есть неявные допущения. Это легко проверить, так как уже при 3-х голубоглазых островитянах, индукция не выполняется - все остаются на острове.
Отсюда вывод - даже строгие математические вычисления нельзя применять бездумно, в отрыве от логики и смысла задачи.
Еще один вывод, более спорный - чем сложнее метод решения, чем выше уровень абстракции, тем легче допустить такого рода ошибку. Поэтому чаще всего самое простое корректное решение является самым верным. Другой вопрос, что наши представления о корректности и простоте могут быть не вполне адекватными.
P. S.: эту ошибку можно объяснить и подменой кванторов, ага.
Для того, чтобы работала математическая индукция, необходимо, чтобы все думали одинаково и приходили к одинаковым выводам, то есть все одновременно (и своевременно) догадались о такой возможности определить свой цвет глаз. Не сказал бы, что если бы мне произнесли такую банальную фразу, как турист, в обычной жизни (предполагается, что аборигены не сидят с утра до вечера, пытаясь свой цвет глаз определить:)))
ОтветитьУдалитьВ остальном, конечно, полностью поддерживаю вариант 2.
> А если не уедет, значит он видит другого голубоглазого - меня.
ОтветитьУдалитьСтоп-стоп. Почему это "меня"? Не "меня", а одного из жителей острова.
Уметь придумывать неправильные решения - крайне полезно для учителя, так как помогает лучше понять учеников, но вредно для ученика, так как отвлекает от понимания правила.
ОтветитьУдалитьТак что, на мой взгляд, читателям правильнее предлагать сегодняшнюю задачу, а вчерашняя - для другой аудитории.
sejros:
ОтветитьУдалитьВы заблуждаетесь. Пусть на острове трое голубоглазых. Каждый из голубоглазых считает, что всего голубоглазых двое или трое (в зависимости от того, какие глаза у него самого). Он также знает, что если голубоглазых двое, то через день они должны уехать с острова. Но они не уехали, значит, голубоглазых трое, значит, цвет глаз ясен. Добро пожаловать в Ад.
Я так и не понял - сами аборигены знают то сколько всего должно быть голубоглазых и сколько карих на острове?
ОтветитьУдалитьВторое решение выглядит неверным. Ошибка в базе индукции - в ней сообщение американца несет новую информацию о наличии голубоглазых, которая в данном случае была у всех
ОтветитьУдалитьcolog:
ОтветитьУдалитьДа, действительно, при Г=3 индукция выполнятеся. Она вообще, корректна. Но, все же я склонен рассматривать эту задачу с точки зрения парадоксальность, а не только с математической.
Турист действительно не сообщил островитянам новой информации. Однако, решение оцвете своих глаз каждый островитянин принимает не столько на основе слов туриста, информацию из которых он уже знал, сколько на основе анализа поведения других островитян.
Теперь такое рассуждение. При Г=N>3 каждый голубоглазый принимает решение на основе моделирования рассуждения остальных при различных вариантах его собственного цвета глаз. Причем некоторые варианты этих рассуждений априори не могут осуществиться, так как опровергаются действительностью. Так, если раскрывать вложенность рассуждений при Г=3, то часть логических выводов будет говорить о том, что Г=2 и в дальнейшем неявно предполагать это. В этом случае, любые двое из трех на первый день не уедуд не потому, что Г=1 или Г=2, а потому, что Г=2 или Г=3. Поэтому, рассуждения, приведенные Вами не правомерны. И, если мы полагаем жителей острова математически грамотными, они должны понимать это. Значит, они не смогут построить свое рассуждение описанным образом.
Как-то так.
Чувствую, что объяснил путанно...
sejros:
ОтветитьУдалитьМне все-таки кажется, что если у островитян есть строгое неопровержимое доказательство поведения своей популяции при Г=2, то они будут использовать его, не задумываясь о каких-либо других способах рассуждения.
Попробую пояснить. Эта мысль родилась у меня только что во время изучения парадокса узника (парадокса неожиданной казни), хотя там немного другая история. Как и в том парадоксе на следующем шаге индукции (на втором точно, насчет последующих не уверен) субъект размышления использует предпосылки, противоположные выводам, использовавшимся на предыдущем шаге.
ОтветитьУдалитьВ данной задаче, естественно, самая суть не в методе индукции а в отношениях знания между субъектом и объектом знания, как и в задаче про узника. Это как деление - просто в некоторых случаях корректная математическая операция дает некорректный ответ (вернее незамкнутый относительно исходного поля, но это уже мелочи).
P.S.: Кстати, упомянутый парадокс узника тоже достаточно зубодробителен, хотя, на мой вкус, не так, как эта задача. Рекомендую.
Вообще говоря в любой момент времени до приезда туриста сектанты могли провести подобные рассуждения и дружно отправиться в "Ад", все что дал турист - формальное доказательство базы индукции, турист был нужен для доказательства случая с одним голубоглазым
ОтветитьУдалитьsejros:
ОтветитьУдалить>на следующем шаге индукции (на втором точно, насчет последующих не уверен) субъект размышления использует предпосылки, противоположные выводам, использовавшимся на предыдущем шаге
На следующем шаге индукции или на следующий день? Применяя индукцию, человек размышляет о разных гипотетических ситуациях, и нормально, что одни из них противоречат другим. Но было бы странно, если бы в один из дней островитянин пришел к выводу, противоречащему его рассуждениям в предыдущий день. Все-таки не могли бы Вы привести конкретный пример противоречия при Г=3?
Действительно, правильность одного доказательства не исключает другого.
ОтветитьУдалитьНо, есть один нюанс: любой островитянин может узнать цвет своих глаз случайно. И уехать с острова.
Слава богу, я не сошёл с ума. :-)
ОтветитьУдалитьЯ всё-правильно понял, это было "логическое доказательство". Оно же, ИМХО, верное. Неверно доказательство по индукции. Неверна фраза:
А если не уедет, значит он видит другого голубоглазого - меня. Он может не уехать, так как недостаточно информации для принятия решения. С точки зрения этих голубоглазых ситуация с принятием решения абсолютно симметричная - либо они оба остаются на острове, либо оба уезжают. Не может быть такого, что один уехал, а другой остался и "философствует".
Противоречие в условии задачи.
ОтветитьУдалитьДело в том, что такая популяция не могла существовать. Базу индукции могло бы дать рождение первого же младенца с голубыми глазами. После этого все сваливают в АД в соответствии со вторым решением, т.к. имеется полная аналогия с высказыванием американца - имеется (появился) как минимум один туземец с голубыми глазами. Тут, правда, нужно считать младенца точно таким же сообразительным, как и остальные члены популяции :)
2Evgeny: загвоздочка в том, что сам младенец с голубыми глазами не знает какого они цвета, а значит база не верна
ОтветитьУдалитьневерно первое утверждение. турист дал информацию островитянам. Очень сильно запутывает большое кол-во людей. Если попробовать задачу для 800 кареглазых, 2 голубоглазых, то становится очевиднее, где проговорился турист.
ОтветитьУдалитьДаже если я неправ, это одна из лучших математических задач. Для меня она стерла все границы очевидности.
Закрались сомнения - слова американца привнесли или нет новую информацию. Если они раньше знали, что все они или Г, или К, то с помощью ММИ они бы вычислили, кто есть кто и уехали бы. Что не согласуется с тем, что они живут на острове. Пока ошибки в самом доказательстве я не вижу и это работает для 1, 2, 3, 4 Г на острове. Продолжаю думать все равно.
ОтветитьУдалитьIvan, спасибо за тёплые слова :)
ОтветитьУдалитьalexsmail, я не понимаю Вашего возражения.
Конечно не может так быть, что один голубоглазый уехал, а другой остался. Но это не мешает каждому из них сделать предположение о карем цвете своих глаз. Каждый думает: «если второй уедет на первый день, значит я кареглазый, а если не уедет, значит мы оба голубоглазые».
EvilPartisan, нет, не знают (это второй пункт условия).
Ну вроде уже разобрались, что нельзя думать «если второй уедет на первый день, значит я кареглазый, а если не уедет, значит мы оба голубоглазые» — человек может уехать не потому, что пришёл к выводу о цвете своих глаз, а просто случайно узнал, что возможно по условию. Так может уехать сразу два голубоглазых на первый же день — просто им не повезло.
ОтветитьУдалитьОднако если хотеть узнать цвет, то по-прежнему можно назначить день Х и с вероятностью, близкой к 1, оказаться правым, т.к. ошибка будет только в случае, когда все, кроме одного, с общим цветом глаз случайно узнали и уехали — но даже тут ошибка заключается лишь в том, что определить цвет не получилось, а не в том, что цвет оказался определён неправильно.
А мне кажется, неверная посылка состоит в том, что все голубоглазые ОДНОВРЕМЕННО начинают проводить одинаковые рассуждения. Если они жили на этом острове до приезда туриста, то знали о наличии других голубоглазых и у каждого из них был свой момент начала подобных рассуждений.
ОтветитьУдалитьЕсли голубоглазый всего один, но он откуда-то (генетическая память :-) ) знает, что голубоглазые есть, то он, разумеется, в тот же день уедет в АД и за ним последуют все остальные.
Но если их двое и задумываться они начинают в разные дни - то вот здесь уже индукционный переход не работает! Тот, кто начал думать раньше, видит всего одного голубоглазого и, видя, что тот не уезжает, не имеет права делать вывод, а том, что он сам тоже голубоглазый, потому что не уверен в том, что второй думает о цвете своих глаз!
Способ решения тут влияет на ответ, поскольку мы думаем за тех, кто тоже умеет думать.
ОтветитьУдалитьРешение подопытных зависит от того, какой из способов рассуждения выберут они сами.
Всё зависит от того, а) додумаются ли они до индуктивного метода, б) додумаются ли все они до него и в) будут ли они уверены, что все додумались. Например, как надо поступать, если на N-й день срывается примерно половина голубоглазых, потому что остальные не просекли фишку с индукцией?
Все, я понял! Ключевая фраза: "Способ решения тут влияет на ответ". Вы абсолютно правы. Так как мы полагаем жителей острова "абсолютными логиками", то в зависимости от того, какой метод рассуждения мы используем и считаем правильным, этот же метод мы приписываем островитянам. ММИ неявно предполагает, что сам ММИ абсолютно корректен и дает однозначный ответ. Значит островотяне ведут себя так, как было описано выше. Если, А, то В, а из В следует А. Следовательно А - верно. Вот ошибка в рассуждениях.
ОтветитьУдалитьПосмотрим на это все с точки зрения островитянина.
ОтветитьУдалитьДа, он действительно знает метод математической индукции. Он понимает его для 2ух человек (если сегодня не уехал первый, то так как кроме него на острове сплошные кареглазые, то нам надо бы свалить в ад на второй день вместе). Также он понимает задачу и для троих собратьев, в таком случае надо уежжать на 3ий день, если двое не уехали на 2ой.
Продолжая рассуждение можно прийти к выводу, что если ты видешь 110 голубоглазых вокруг, то есле они не уежжают за 110 дней, то ты должен на 111 быть готовым к отплытию.
Но без туриста тут довольно неприятная ситуация, которая заключается в следующем: с какого момента времени отсчитывать 110 дней?
И хоть информация о наличии голубоглазых в словах туриста не нова, само его сообщение служит точкой отсчета дней.
2Quazz:
ОтветитьУдалитьПоскольку ген карих глаз - доминантный, а голубых - рецессивный, то родившийся младенец тоже может дать базу индукции в виде дополнительной информации. Если у него глаза голубые, то хотя бы один из обитателей тоже должен иметь голубые глаза. Ну а далее все аналогично второму решению :).
Этот комментарий был удален автором.
ОтветитьУдалить2Plushkin Kot:
ОтветитьУдалитьПросто точка отсчета не сработает. Ну праздник, предположим. И что? Если на острове 1 голубоглазый, он об этом не знает. Если 2 - то им неизвестно их количество. Ситуация с американцем отличается тем, что даже если бы на острове был один голубоглазый, об этом после слов американца узнали все, ВКЛЮЧАЯ САМОГО ГОЛУБОГЛАЗОГО. В случае случайного события (праздник) это не происходит.
Почему приведенное в посте доказательство индукцией неверное:
ОтветитьУдалитьНачало хорошее, есть один голубоглазый, ему сказали, он уехал.
Тут для запутывания приведен пример с 2, хотя он уже не совсем верный (один из них уезжает после того, когда уверен что время для принятия решения первым в случае одного жителя гарантированно прошло, а не на следующий день).
А теперь что мы принимаем:
"И он понимает, что если цвет его глаз не голубой, то они все уедут на N-ный день (по предположению индукции)." Внимание, островитянин решил что у него итерация индукции занимает один день. А второй островитянин думает про срок итерации полдня (все ведь видят тех кто уезжает). Опа, они все понимают что могут думать по разному. Как они будут полагатся на длительность итерации в один день без предварительного сговора?
И так что мы имеем: есть доказательство что ничего не поменяется (верное). Вывод: ничего не поменяется.
2pcholberg
ОтветитьУдалитьВременной интервал определяется расписанием парома в АД.
pcholberg:
ОтветитьУдалить>Внимание, островитянин решил что у него итерация индукции занимает один день. А второй островитянин думает про срок итерации полдня (все ведь видят тех кто уезжает). Опа, они все понимают что могут думать по разному. Как они будут полагатся на длительность итерации в один день без предварительного сговора?
Действительно, тут небольшая проблема. Ее можно устранить, если добавить в задачу условие, что определившие свой цвет глаз до 17:00 мгновенно телепортируются на другой остров ровно в 17:00. Или, что немного сложнее, но более реалистично, в 16:00 все жители острова уединяются в своих хижинах, закрыв глаза и уши, а узнавшие цвет глаз на цыпочках выходят и движутся к парому.
Когда американец во всеуслышанье говорит, что "на острове есть хотя бы один Г", то это делает для остальных очевидными два факта:
ОтветитьУдалить1. на острове есть Г
2. все знают, что на острове есть Г
Рассмотрим случай, когда Г=2. Тогда каждый из них заранее знал (1), но не был уверен в (2): "если я не Г, то второй единственный, и он не знает, что он Г".
В случае Г=3. Каждый Г знал и (1), и (2): "даже если я не Г, то эти двое друг друга видят, и знают, что Г есть".
Получается, что в случае Г=3 американец не сообщил им ничего нового, а раз так, то его утверждение не может инициировать индукцию, т.к. эта индукция должна была быть уже выполнена раньше (данные-то те же самые у всех остались).
Сан Саныч:
ОтветитьУдалитьВы забыли утверждение 3 - все знают, что все знают, что на острове есть Г. Каждый Г до приезда туриста знал (1) и (2), но не (3).
все знают, что все знают, что на острове есть Г: если один видит троих Г, то он знает, что каждый из них видит не менее двоих Г, а следовательно, все в курсе, что есть не менее двоих Г.
ОтветитьУдалитьТут еще есть тонкость. При построении этой индукции неявно предполагается некорректное обобщение: считается, что при ЛЮБОМ количестве Г на острове (включая Г=1) американец будет при прощании произносить свою сакраментальную фразу. А это не так (не обязательно так).
ОтветитьУдалитьИлья Весенний,
ОтветитьУдалитьСуть моего возражения заключается в том, что другой может не уехать так как у него нет достаточной информации. Cм. А если не уедет, значит он видит другого голубоглазого - меня
Quark Fusion:
ОтветитьУдалитьСложно объяснить словами, посмотрите лучше на картинку в случае с Г=3 и К=0. Показаны размышления первого Г о возможном цвете своих глаз и размышлениях других. Все реальные (в нижнем ряду) и почти все "вымышленные" персонажи знают, что на острове есть голубоглазый. Единственное исключение - вымышленный Г справа вверху, над которым поставлен знак вопроса. Он не знает, есть ли на острове Г. Значит, думающий о нем Г не уверен, что все знают, что на острове есть Г. Значит, думающий о думающем не уверен, что все знают, что все знают, что на острове есть Г. Что и требовалось доказать.
Сообщение туриста заставило _всех_ островитян _одновременно_ думать о цвете => 2 решение верное и от сообщения необходимо отсчитывать количество дней
ОтветитьУдалитьААААА! Я долго чесал репу, пытаясь понять, каким таким первое решение может оказаться неправильным. А когда услышал второе, то сразу вспомнил лошадок одного цвета.
ОтветитьУдалитьШаг 1->2 неправильный, короче. Ход мыслей каждого из двух голубоглазых: "Ну да, на острове есть хотя бы один голубоглазый, вон он стоит, а я... а я не знаю какой я." И никому никуда подрываться не нужно.
Если, конечно, не начинать приплетать сюда информацию, полученную невербальным путём. Два товарища, которые, в отличие от всех остальных, начинают после визита американца зырить друг на друга и чесать репу, таки оказываются на пароме в этот же день.
ОтветитьУдалить---:
ОтветитьУдалитьТогда уж и база индукции тоже неправильная. Ход мыслей единственного голубоглазого: "ЛА-ЛА-ЛА Я НИЧЕГО НЕ СЛЫШАЛ ЛА-ЛА-ЛА Я НИЧЕГО НЕ СЛЫШАЛ", и все остаются на острове ;-)
ЛА-ЛА-ЛА Я НИЧЕГО НЕ СЛЫШАЛ =)))
ОтветитьУдалитьвывод: умные попадают в ад!
Согласен, облажался. Шаг 1->2 можно считать правильным. А вот 2->3 - точно неправилен.
ОтветитьУдалитьA если детально разбираться, что же тут не так, то подвох открывается в путанице на этапе шага индукции. Утверждение "Если на острове N голубоглазых, и все они за N-й день уезжают, то N+1 голубоглазых уедут за N+1 день" - неверно, так как условия "все N голубоглазых уехали за N дней" и "N из N+1 голубоглазых уехали за N дней" - существенно разные условия. В "доказательстве" же они мило подменяются одно другим.
N из N+1 голубоглазых уехали за N дней" - этого никто и не утверждает, наоборот)
ОтветитьУдалитьвсе Г уедут одновременно (если, как утверждается в условии, они все мыслят как клоны).
---
ОтветитьУдалитьНо шаг 2->3 тоже правильный - в этом можно убедиться непосредственно, используя уже доказанное утверждение о двоих голубоглазых.
Нигде в доказательстве не утверждается и не предполагается, что N голубоглазых уплывут, а (N+1)-ый останется. Он остался бы (на день дольше голубоглазых), если бы был кареглазым, и надеялся на это до последнего, как, кстати, и остальные голубоглазые, рассуждавшие точно так же. Но так как в соответствующий день никто из надеющихся на свое кареглазие голубоглазых не уехал, они отбросили свои надежды и уехали следующим рейсом.
хм... действительно. ;)
ОтветитьУдалитьНо. Если индукция правильная, и отсчет дней запускается (на первый взгляд) лишь информацией о том, что "среди островитян есть Г", то что мешает островитянам самим запустить этот отсчет? Они же и сами видят, что среди них есть Г. Далее: каждый из тех, кто видит 110 Г, начинает считать 110 дней... не проходит. почему?
Потому что нету синхросигнала, напрашивается ответ?
А если раскрутить эту индукцию по-иному?
Если бы на острове был 1 Г, то утверждение "все знают, что среди нас есть Г" было бы неверно. Единственный Г - не знает.
Если бы было 2 Г, то они могли бы сосуществовать, только приняв, что "возможно одно из двух: или я Г, или я не Г, но тогда этот второй Г не знает, что среди нас есть Г". Т.е. он допускает, что не все знают, что среди нас есть Г.
Если бы было 3 Г, то каждый из них думал бы: "возможно одно из двух: или я Г, или я не Г, но тогда эти двое допускают, что не все знают, что среди нас есть Г". Он допускает, что кто-то допускает, что не все знают, что среди островитян есть Г.
Если бы было 4 Г, то они бы думали: "или я Г, или эти трое допускают, что кто-то допускает, что не все знают, что...". Он допускает, что кто-то допускает, что кто-то допускает, что... .
Соответственно, обобщим. Каждый из 111 голубоглазых допускает, что он может быть как голубоглазым, так и кареглазым, но при этом он допускает, что кто-то допускает, что кто-то (до умопомрачения много звеньев) допускает, что среди островитян есть Г.
Остальные кареглазые рассуждают точно так же - каждый мог оказаться 112-м Г, или не оказаться, допуская, что кто-то допускает, что ... ну вы поняли.
Когда американец сказал во всеуслышание "среди вас есть Г", ни для кого не осталось возможности допускать, что среди островитян нет Г. Более того, ни для кого не осталось возможности допускать, что кто-то допускает, что среди островитян нет Г. Более того, ни для кого не осталось возможности допускать, что кто-то допускает, что кто-то допускает, что среди островитян нет Г. И так во всех порядках сразу.
Вот что сказал американец островитянам, и именно поэтому они все, действительно, низбежно должны уехать. Похоже, мне прижется признать свою ошибку. Впрочем, это уж по-любому: ошибся я или в предыдущих рассуждениях, или в этом ;)
---------
ОтветитьУдалитьЕсли бы было 3 Г, то каждый из них думал бы: "возможно одно из двух: или я Г, или я не Г, но тогда эти двое допускают, что не все знают, что среди нас есть Г". Он допускает, что кто-то допускает, что не все знают, что среди островитян есть Г.
---------
Если уж прибавлять по одному, то будет так:
к двоим г прикатил неизвестный. Он точно видит двоих г. Он точно знает, что каждый из них видит г и знает про г.
И не важно, что они могут допускать, что кто-то из них допускал до привоза второго, они уже все знают, что г точно есть.
Так что из всего этого выходит только один итог:
если бы остров заселяли с нуля, то заселив двоих или менее голубоглазых, без нарушения условия они сразу бы определили свой цвет на условии того, что условие не могло быть нарушено.
А раз они все живут - значит итогом будет факт того, что на остов первыми ступили минимум 3 голубоглазых одновременно.
P.S.
И что по основной задаче:
раскручивая от большего к меньшему возникают противоречия: каждый бы думал что думают другие голубоглазые, тогда как лично он (а значит и каждый голубоглазый) думал бы совсем иначе (а именно о том, как думают другие).
И пока каждый будет думать о том, как размышляют другие о всех, вместо того что бы размышлять так, как думает каждый другой о нем - никто никуда не уедет.
А с тем учетом что каждый не знает, как о нем размышляют другие (как о г, или как о к), никто никогда не сможет начать думать именно так, как надо.
Все же я склонюсь к варианту, так или иначе тут уже прозвучавщего и в моем понимании дающем логическую связь для ММИ.
ОтветитьУдалитьИнформация от американца не изменила ничего в плане новых знаний - это факт при Г > 1. В остальном - это послужило событием, точнее двумя:
1) запустило мыслительный процесс (логическую цепочку, которая верно доказана с помощью ММИ) - ОДНОВРЕМЕННО;
2) как следствие из 1) - дало точку отсчета.
Мне это напоминает введение системы координат - в реальности ее нет, но абстрактно вводя ее мы строим математику :)
Так и представляю картину:
ОтветитьУдалитькаждый день всё стадо приходит на паром (посмотреть, не уедут ли другие), а через 110 дней 111 из них делают шаг вперед.
На деле каждый из них знает, что каждый из них может видеть минимум 110, а максимум - 112 голубоглазых. Значит в первые 108 дней приходить бессмысленно.
На 109 день каждый будет ждать шага других.. никто не зайдет.
На 110 день каждый, кто видел 110 голубоглазых сделает шаг, останутся те, кто видел 111 голубых пар (глаз, разумеется, не людей).
Так, выходит?
Остается вопрос за малым: послужила ли фраза туриста точкой отсчета?
В условии не указано, что все сектанты думают идентично:
один может не придать значение такой фразе (первый вариант решения), другой может начать отсчет с сегодняшнего дня, третий - с завтрашнего.
И тут уже не важно как думает каждый, но каждый догадается в неоднозначности точки отсчета. А допуск ошибки в 1 день не позволит каждому быть уверенным в правоте определения цвета своих глаз.
Итог - все останутся. Как минимум из-за неточности условий задачи.
---
ОтветитьУдалитьЕсли уж прибавлять по одному, то будет так:
к двоим г прикатил неизвестный. Он точно видит двоих г. Он точно знает, что каждый из них видит г и знает про г.
И не важно, что они могут допускать, что кто-то из них допускал до привоза второго, они уже все знают, что г точно есть.
---
А вот и нет. Просто знать, "что Г точно есть", мало - это все и так знают. Обратите внимание: если бы американец сказал это же каждому по отдельности, на ушко - то ответ был бы, действительно, "ничего не изменилось". А он сказал громко и при всех. Поэтому мало того, что все услышали, что на острове есть Г.
Все поняли, что все услышали, что на острове есть Г.
Все поняли, что все поняли, что все услышали, что на острове есть Г.
Все поняли, что все поняли, что все поняли, что все услышали, что на острове есть Г.
И так далее.
Это таки больше информации, чем просто одна первая строчка.
И приведенная задачка живо иллюстрирует как раз эту разницу - "все знают" vs. "все знают, что все знают, что все знают, ... что все знают".
А зачем тут вообще доказывать по индукции? "Если бы был 1, если бы было 2, если было 3".... их 111, а не 1 и не 2.
ОтветитьУдалитьcolog картинкой показал даже на примере простого множества, что вариантов куча, и ни один сектант решения не примет.
Никто не знает, никто не будет уезжать ни в первый день, ни в 110, ни в 111.
> И приведенная задачка живо иллюстрирует как раз эту разницу - "все знают" vs. "все знают, что все знают, что все знают, ... что все знают".
ОтветитьУдалитьОни и раньше знали что все знают что есть Г, т.к. Г по острову бродит большая толпа. И Г ты или К не влияет - кроме тебя ещё куча Г, поэтому все знают что есть Г, поэтому все знают что все знают что есть Г, независимо от своего цвета.
---, Игорь Говорунов:
ОтветитьУдалитьВо-первых, любой житель острова ТОЧНО знает, что Г на острове есть, по крайней мере 110 штук, поэтому им незачем это допускать.
Во-вторых, все островитяне по условию одинаково умные и в одинаковых условиях, причем ДОСТАТОЧНО умные чтобы догадаться до вышеизложенного ММИ. Так что, либо они-таки догадаются (одновременно) об этом и все уедут, либо ВСЕ не догадаются и останутся (возможно в том случае, если все они не так чтобы все время думают о цвете своих глаз, и не увидели в словах туриста сакрального смысла:)))
Я себе это так представляю.
Коротко говоря, второе решение содержит 2 ошибки.
ОтветитьУдалить1. Общая. Турист не сообщил новой инфы. Метод мат индукции неприемлем, поскольку, если турист не сообщил новой инфы, применяя метод мат. индукции, догадливые жители применили бы его сразу и уехали (по условию, они всегда догадываются до всего, до чего могут догадаться). То есть, их на острове не было бы.
2. Метод был бы приемлем если бы с каждым шагом индукции прибавлялось бы по одному голубоглазому. В нашем случае, начиная с 2 шага (3Г) мы совершаем ошибку. Вывод о цвете однозначен только при 2 г. 3 же будут до бесконечности ждать. Вот если появляется по 1 г в каждом шаге так, что результат шага он видит, а остальные прибывшего - нет, тогда метод будет работать.
---, поздравляю с озарением =)
ОтветитьУдалитьИгорь Говоров, вы неправильно интерпретировали мою картинку. На ней не все сектанты (точнее говоря, не все их мысленные образы) знают, что на острове есть голубоглазый. Это образ сектанта справа вверху, помеченный знаком вопроса. И хоть он существует только в мыслях образа второго сектанта, находящегося в голове первого, после фразы туриста он единственный на картинке сразу определит свой цвет глаз и уедет первым паромом. Теперь у мыслеобраза второго сектанта появилась возможность отличать вымысел от реальности: если третий уехал, значит реальность справа, не уехал - слева. На второй день ему в любом случае становится известен цвет глаз, и он уезжает. Теперь первый сектант, уже настоящий, отличает вымысел от реальности по поведению второго сектанта: если он уехал на второй день, то реальность справа, не уехал - слева. И на третий день узнает свой цвет глаз и уезжает. Аналогично рассуждали второй и третий сектанты (не мыслеобразы, а настоящие) и тоже уехали на третий день.
Если б не турист, мыслеобраз третьего сектанта так никогда и не узнал бы свой цвет глаз и не запустил бы цепную реакцию.
"---" Браво! После вашего коментария даже я панял что сообщение туриста таки принесло дополнительную информацию. А именно теперь все знают что все знают, что все знают ... и так 111 раз. До сообщения туриста жители с голубыми глазами видели только 110 соплеменников Г и поэтому знали лишь цепочку длиной 110.
ОтветитьУдалитьС таким же успехом можно через ММИ докузывать, что n*n=n:
ОтветитьУдалить0*0=0
1*1=1
=>
2*2=2 ))
Интересная ссылка по теме:
http://physics-animations.com/matboard/themes/7753.html
elhana, Вы привели пример не ММИ, а "рассуждения по аналогии". Вообще говоря, это бытовое рассуждение, которое к математике не относится.
ОтветитьУдалитьЯ же выше привёл корректное доказательство. Или покажите в нём ошибку, или не путайте :)
colog и ---, поздравляю с озарениями! Вы очень точно и грамотно излагаете. Уважаю! :)
Между прочим, К в 5 раз больше Г на острове, потому каждый вправе предполагать что он К. Это удобно при размышлениях о вариантах: (N) предполагает что он К, тогда - как он думает - каждый (N-1) предполагает, что он К и про каждых (N-2) думает, что (и т.д.)
ОтветитьУдалитьУпс, даже в 8 раз больше. Ну тем более
ОтветитьУдалитьДавай вспомним, что такое ММИ (в простейшем случае), и когда он применим.
ОтветитьУдалитьПусть есть некий предикат P(n), про который известно:
1) P(1)
2) для любого натурального n выполнено: P(n) => P(n+1)
Тогда для любого натурального n выполнено: P(n).
В нашей задачи в роли предиката P(n) хочет выступить утверждение:
"если на острове есть N голубоглазых и больше N кареглазых сектантов, то на N-ный день все голубоглазые узнают цвет своих глаз и уедут. А все кареглазые узнают цвет своих глаз и уедут на N+1-ый день".
Проблема в том, что это не предикат в том смысле, что он не поддается формализации. Что означает "узнать цвет глаз"? Построить цепочку выводов утверждения "мои глаза имет цвет X"? Или как-то иначе? И вообще, как формализовать процесс мышления (а это необходимо для применения математических методов) для этой задачи? Более того, фраза "все островитяне очень умные,
поэтому они догадаются до всего, до чего только можно догадаться" тоже весьма и весьма туманна. "Можно догадаться" исходя из каких соображений?
Попытаемся ответить на эти вопросы:
1) мышление. У каждого островитянина есть свой конечный набор аксиом (наблюдаемых явлений) и конечный набор правил вывода. Догадаться до чего-либо - значит построить соответствующее доказательство, используя аксиомы и правила вывода.
2) "можно догадаться" понимается как всякое выводимое утверждение (или его отрицание) уже известно.
3) Утверждение "мои глаза цвета X" и эквивалентные ему невыводимо.
Когда иностранец произносит свое заклинание, ни у одного из островитян не появилось новых выводимых утверждений, поскольку высказывание "на острове существует Г" выводимо у КАЖДОГО островитянина. И все живут как раньше.
Из такой интерпретации следует, что ничего не изменится. Как же быть с индукцией?
А индукция тут неприменима, т.к. доказываемое ММИ утверждение невозможно описать данной интерпретацией - невыводимое утверждение не становится выводимым через N суток.
Это означает, что предложенная интерпретация "ущербна" в том смысле, что в ней не работают доказательства, допустимые в других (если таковые существуют).
Наверное, существуют и другие интерпретации, в которых эта индукция работает, но формально это ДРУГАЯ МАТЕМАТИЧЕСКАЯ задача.
Лично я не могу придумать такую интерпретацию, в которой работает индукция. Можно, наверное, попытаться доказать, что их не существует.
Итак, мне представляется, что эта задача из разряда "Идут два человека, чистый и грязный. Кто идет в баню?". Это нематематическая задача, поэтому возможны принципиально разные ответы (через разные способы перевести условие на мат. язык).
--
Kirill
Kirill:
ОтветитьУдалить>Когда иностранец произносит свое заклинание, ни у одного из островитян не появилось новых выводимых утверждений, поскольку высказывание "на острове существует Г" выводимо у КАЖДОГО островитянина.
Вот здесь-то и кроется ошибка - турист сообщил нечто большее, чем просто "на остове существует Г". Потому что до приезда туриста из бесконечного списка утверждений:
1) на острове есть Г
2) все сектанты знают, что (1)
3) все сектанты знают, что (2)
...
были выводимы только первые несколько или ни одно, а после его отъезда - все множество.
colog:
ОтветитьУдалить> Вот здесь-то и кроется ошибка - турист сообщил нечто большее, чем просто "на остове существует Г".
Что-то туплю... Как тогда формулируется та информация, которую собщил иностранец (какая аксиома добавилась, что все высказывания стали выводимы)?
--
Kirill
И все же, поясните мне, пожалуйста, насколько корректно обобщение, про которое я упоминал выше. То есть во 2-м доказательстве неявным образом подразумевается, что американец будет произносить свою прощальную фразу при любом количестве Г на острове, включая N=1. Это ниоткуда не следует, соответственно метод индукции здесь не применим.
ОтветитьУдалитьГде я неправ?
Kirill: так и формулируется - верны утверждения (1), (2), (3) и т. д. Турист мог бы сказать это каждому по отдельности на ухо, что привело бы к точно такому же результату, как и публичное высказывание "верно утверждение (1)", потому что утвержения (2), (3), ... выводятся из (1) и публичности. А вот если сообщить только лишь утверждение (1) каждому по секрету, ничего не произойдет.
ОтветитьУдалитьПоправка: если сообщить только лишь утверждение (1) каждому по секрету, ничего не произойдет при Г>1
ОтветитьУдалитьEvgeny: дело в том, что в доказательстве рассматривается не сам турист с его мыслями и чувствами, а некое существо, ведущее себя в точности как наш турист при Г=111, К=888 и как нам хочется при других значениях Г и К. Может быть, существо, увидев одинаковое количество голубоглазых и кареглазых, сжирало бы их всех - это не имеет значения, если удастся доказать, что при Г=111 и К=888 повстречавшие существо островитяне уезжают через столько-то дней. Тогда, очевидно, американский турист приведет к тому же результату.
ОтветитьУдалитьНо чтобы доказательство получилось простым и красивым (или получилось вообще), существо просто всегда говорит одну и ту же туристову фразу - "на острове есть как минимум один голубоглазый".
Реально индукция не применима.
ОтветитьУдалитьМысль может пойти так.
Г видит, например, десять голубоглазых. Он думает, что каждый из них видит девять Г.
Каким образом можно от того, что каждый уверен, что Г видит девять Г, а не десять пойти по индукции дальше? Ведь каждый Г не сможет подумать, что какой-то Г увидит восемь.
Хотя до какого-то предела похоже, что есть индукция.
colog:
ОтветитьУдалитьПонял :-) В своей интерпретации я не смог научить сектантов думать за других :-) Поэтому и вывод такой невозможен.
Предположим, на острове N+1 Г. Каждый Г думает так:
ОтветитьУдалить«Вас, Г, либо N, либо N+1 вместе со мной. И если я К, то любой, например ты, Вася, думаешь, что если ты тоже К, то остальных будет N-1, каждый из них будет в свою очередь тоже воображать, что он К и всех Г N-2, и так далее. Но я-то знаю, что про N-1 не думает никто, потому что видит перед собой не только N-1 остальных умников, но и Васю, который тоже полнейший Г. (Ну а если я К, то никто не будет думать про N по той же логике, и так мы никогда не доберемся до единицы.) И еще я знаю, что ты, Вася, придешь к такому же выводу, неважно, насчет N-2 (если я К) или насчет N-1 (если я Г), потому что сам видишь, сколько здесь этих Г развелось помимо тебя. Я даже знаю, что ты будешь уверен, что твой дружбан Коля так подумает насчет N-3 или N-2, но я знаю еще больше — он будет думать точно так же, как ты, потому что видит вокруг себя такое же количество Г, а я еще и вижу, что и сам он Г, это не говоря о том, что я сам, возможно, тоже Г. Поэтому до N-3 никто реально даже не дойдет, кипеш поднимать не будем, дураков нет. Все остаются на острове.»
Индукция предполагает, как мыслил бы один Г, основываясь на возможных мыслях второго, основанных в свою очередь на возможных мыслях третьего и т. д., но дело в том, что первый хорошо понимает, что такие мысли третьего могут существовать только в воображении второго, который не знает, что он Г, а первый знает, что второй Г, и поэтому в дальнейшую индукцию не углубляется.
Vovix: все-таки метод математической индукции - это процесс накопления доказательств некоторого утверждения при N=1, затем 2, 3 и т. д., только вместо того, чтобы доказывать бесконечно много утверждений по заданному шаблону, доказывают, что по такому шаблону можно доказать любое из них. А вы называете индукцией просто размышления островитян.
ОтветитьУдалитьЕсли они рассуждают по индукции, то сначала доказывают, что единственный Г уезжает в первый день, потом, используя этот факт, что двое Г уезжают через два дня, потом, используя два предыдущих факта, что трое Г уезжают через три дня и так далее по одному и тому же шаблону. Потом им надоедает доказывать однотипные утверждения, и они доказывают, что шаблон (то есть шаг индукции) позволяет доказать все такие утверждения.
Если же они рассуждают сложным способом, как описали Вы, то нужно помнить, что островитяне не испытывают проблем с логикой и не пасуют перед высказываниями тройной и даже стократной глубины вложенности. Турист дал достаточно информации, чтобы можно было отсечь некоторые совсем уж фантастические варианты на глубоких уровнях вложенности и запустить оттуда цепную реакцию, приводящую к отсечению с каждым днем все менее глубоких и все более реальных вариантов.
>Вот здесь-то и кроется ошибка - турист сообщил нечто большее, чем просто "на остове существует Г". Потому что до приезда туриста из бесконечного списка утверждений:
ОтветитьУдалить>1) на острове есть Г
>2) все сектанты знают, что (1)
>3) все сектанты знают, что (2)
Все эти утверждение доказуемы и до высказывания туриста. Докажем это перебором возможных вариантов:
А) Сектант К. Он видит вокруг 111 Г, и понимает что утверждение (1) истинно. Он также понимает, что в зависимости от цвета его глаз, остальные видят либо 112 либо 111 Г, что значит (2). Так как каждые К может рассуждать так же, доказали (3) и так далее для К.
Б) А) Сектант Г. Он видит вокруг 110 Г, и понимает что утверждение (1) истинно. Он также понимает, что в зависимости от цвета его глаз, остальные видят либо 111 либо 110 Г, что значит (2). Так как каждый Г может (и будет, раз они все одинаковые роботы) рассуждать так же, доказали (3) и так далее для каждого К.
Илья:
ОтветитьУдалить> Я же выше привёл корректное доказательство. Или покажите в нём ошибку, или не путайте :)
Kirill выше подробно и дотошно расписал почему это доказательство не может быть правильным с точки зрения логики и тождественного множества посылок в обеих случаях.
Предложение опровергнуть провокационное и напоминает мне Чайник Рассела.
colog комментирует...
ОтветитьУдалитьQuark Fusion:
Сложно объяснить словами, посмотрите лучше на картинку в случае с Г=3 и К=0. Показаны размышления первого Г о возможном цвете своих глаз и размышлениях других. Все реальные (в нижнем ряду) и почти все "вымышленные" персонажи знают, что на острове есть голубоглазый. Единственное исключение - вымышленный Г справа вверху, над которым поставлен знак вопроса. Он не знает, есть ли на острове Г. Значит, думающий о нем Г не уверен, что все знают, что на острове есть Г. Значит, думающий о думающем не уверен, что все знают, что все знают, что на острове есть Г. Что и требовалось доказать.
colog, не обязательно рассматривать случаи с Г=2 и ниже, что вас ограничивает идти до начала ряда натуральных чисел? Почему вы не рассматриваете что думает вымышленный Г в случае Г=0? :) А в случае Г=-1? (пусть это будет вооброжаемый Г, которого воображают все сразу и думают, что он на самом деле есть, хотя его никто и не видит)
Мы тут думаем по принципу если алгоритм верен для Х и верен для Х+1, то мы доказываем непрерывность возрастания функции на интервале [X;+∞), что означает, что алгоритм будет верен для всех Х+А, где А>0 — для А<0 мы ничего не доказываем и не рассматриваем эти случаи, как выходящие за область определения. Нас вроде никто не ограничивает принимать Х=1.
--- комментирует...
ОтветитьУдалить[...]
Соответственно, обобщим. Каждый из 111 голубоглазых допускает, что он может быть как голубоглазым, так и кареглазым, но при этом он допускает, что кто-то допускает, что кто-то (до умопомрачения много звеньев) допускает, что среди островитян есть Г.
"---", последнее предположение о том, что "кто-то допускает" становится неверно при Г=3, т.к. ясно для всех Г, что Г>1, если Г=2, то человека, думающего об этом это уже не волнует, т.к. он знает, что он не Г, т.к. сам видит 2 Г — следовательно, если всё-таки Г=2, то те бы двое видели Г=1, до всего бы догадались и уехали. Как только стало ясно, что Г≠2, то можно думать, что Г=3 — а далее по цепочке.
Никакого предположения "что кто-то допускает" уже нет.
Илья Весенний комментирует...
ОтветитьУдалить[...]
colog и ---, поздравляю с озарениями! Вы очень точно и грамотно излагаете. Уважаю! :)
Я всё-таки по-прежнему считаю, что не было такого "подвешенного" состояния, когда последний из воображаемых воображаемыми считает, что нету Г. Это утверждение (что нет Г) развеевается как только Г≥3. Ваша индукция не учитывает всей имеющейся информации — то что Г≥3 заранее всем известно.
Единственное новое, что сказал турист — начало точки отсчёта.
Так, кажется тут некоторые кое-что путают в ММИ:
ОтветитьУдалитьДопустим, что
1. Установлено, что P1 верно. (Это утверждение называется базой индукции.)
2. Для любого n доказано, что если верно Pn, то верно Pn + 1. (Это утверждение называется индукционным переходом.)
Тогда все утверждения нашей последовательности верны.
Тут Р1 это не Г=1, а Г=3! Случай Г=3 мы доказываем отдельной индукцией, для которой известно, что есть Г из второй!
Vovix, тут индукция нужна, чтобы прийти к мысли о запуске таймера, по которому станет ясно Г=N или Г=N+1 для того, кто наблюдает сколько всего Г. То есть каждый решает свалить в день по количеству наблюдаемых Г, и если к тому дню все наблюдаемые Г еще не свалили, то он прав и он Г и должен свалить вместе со всеми, а если свалили — то он не Г. И не важно какие цвета глаз ещё существуют — если сказали про Г, то вопрос только "Г или не Г".
ОтветитьУдалитьДальше таймер должен запускаться всеми одновременно с некоторого события, которое можно связать с запуском таймера — сообщение о наличии Г и есть такое событие.
Ещё турист мог оказаться подлецом и сказать, что если тут все были такие умные, то на острове уже бы никого не осталось — результат был бы тот же, информация о наличии Г не важна, т.к. это и так всем известно.
Еще по поводу ММИ:
ОтветитьУдалитьВ википедии описывается принцип домино "домино выставлено в ряд таким образом, что каждая косточка, падая, обязательно опрокидывает следующую за ней косточку" — давайте предположим, что так просто косточки не падают и поменяем условие:
Косточка упадёт только если на неё свалятся сразу две косточки и косточки стоят достаточно близко друг к другу.
Тут одна косточка не вызывает падения домино, но вот уже две рядом стоящие косточки — вызывают и принцип индукции начинает работать только на втором этапе, когда падает вторая косточка. С островитянами всё тоже самое — если думает один или двое, то процесс на них и закончится, но если думают сразу трое — то лавина пойдёт.
мля, как я вас всех ненавижу :) угробили мне кучу времени на размышления!
ОтветитьУдалитьво втором решении в заглавном посте отсутствует доказательство того, что все островитяне думают, что другие думают о том, что все думают о том, какого цвета у них глаза! Фраза туриста не обязана заставлять их об этом думать, так что жизнь на острове изменится, только если все островитяне идентичны и задумались о цвете своих глаз и существовании способа это выяснить без нарушения запрета на обсуждение.
Без этого доказательства второе решение не имеет смысла. А первое решение должно доказать, что островитяне не ищут способа узнать цвет своих глаз из-за боязни существования такого способа (а он есть только если все его ищут).
Quark Fusion, не Вы первый предлагаете мысль о "запуске таймера". Но в чём она состоит? Разве в условии оговорено, что островитяне обязаны одновременно начать отсчитывать дни от отъезда туриста? Это непонятное соображение. Оно выглядит как решение, но им не является.
ОтветитьУдалитьИ судя по Вашим следующим замечаниям, Вы ещё не поняли рассуждения для случая трёх голубоглазых на острове.
Вы пишете: «Я всё-таки по-прежнему считаю, что не было такого "подвешенного" состояния, когда последний из воображаемых воображаемыми считает, что нету Г. Это утверждение (что нет Г) развеевается как только Г≥3. Ваша индукция не учитывает всей имеющейся информации — то что Г≥3 заранее всем известно.». Это понятное соображение, но оно ошибочное. Дело в том, что никто не сомневается, что все знают, что Г на острове есть. Но все ли уверены, что каждый уверен, что все знают, что Г на острове есть?
Это совсем другой вопрос! И именно на него ответил турист.
Как только Вы поймёте эту тонкость, многие вопросы исчезнут. Удачи! :)
Quark Fusion, пока я писал Вам ответ, Вы успели оставить новый комментарий :)
ОтветитьУдалитьВы пишете: «во втором решении в заглавном посте отсутствует доказательство того, что все островитяне думают, что другие думают о том, что все думают о том, какого цвета у них глаза», как будто в условии задачи не сказано «Все островитяне очень умные, поэтому они догадаются до всего, до чего только можно догадаться.» Это не надо доказывать, так как это часть условия.
Игорь Говоров:
ОтветитьУдалить>Все эти утверждение доказуемы и до высказывания туриста. Докажем это перебором возможных вариантов
Не все, а только первые несколько, в данном случае 110. В Вашем доказательстве есть арифметические ошибки, кроме того, оно не учитывает исчезновение информации при анализе одним островитянином мыслей другого (первый островитянин знает то, что известно ему одному и обоим, второй - тоже что известно ему одному и обоим, но если первый будет бумать о втором, то второй в голове первого будет знать наверняка только то, что известно обоим).
Вот мое строгое доказательство.
Утверждение 1: на острове есть голубоглазый.
...
Утверждение n: все островитяне знают, что утверждение n-1 истинно.
...
Предположение индукции: островитянин, видящий n голубоглазых, знает все утверждения с номером не больше n и не знает остальные.
База: при n=0 это очевидно.
Шаг индукции. Пусть предположение уже доказано для n=N. Пусть островитянин видит N+1 голубоглазых. Он думает, что сам а) кареглазый или б) голубоглазый.
а) Его соотечественники видят каждый по N голубоглазых. Следовательно, по предположению индукции они знают утверждения с номером не больше N не знают остальные.
б) Они видят каждый по N+1 голубоглазых. Следовательно, они знают утверждения с номером не больше N+1 и не знают остальные.
Так как у нашего островитянина нет сопособа определить, какой из двух вариантов соответствует истине, он может принять за истину только те утверждения, которые истинны в обоих вариантах.
Итак, он точно знает, что соотечественники знают утверждения от 1 до N. Сам он тоже знает эти утверждения. Значит, он знает утверждения от 1 до N+1. Знает ли он утверждение N+2? Нет, потому что в одном из вариантов соотечественники знают N+1, а в другом не знают. Знает ли он утверждения с еще бОльшим номером? Тем более не знает, потому что соответствующие им утверждения соотечественники не знают ни в одном из вариантов. То есть он знает утверждения с номером не больше N+1 и не знает остальные. Что и требовалось доказать.
Никаких трюков с невозможностью первого шага здесь нет - убедитесь сами.
Прошу прощения, в моем доказательстве ошибка.
ОтветитьУдалить>б) Они видят каждый по N+1 голубоглазых. Следовательно, они знают утверждения с номером не больше N+1 и не знают остальные.
Утверждение для N+1 пока еще не доказано, а я уже использую его как доказанное, что делать нельзя. Сейчас буду думать, как ее исправить.
Внимание, предыдущее мое доказательство было ошибочным! А это доказательство еще не завершено, потому что основывается на очевидном, но пока еще не доказанном предположении.
ОтветитьУдалитьУтверждение 1: на острове есть голубоглазый.
...
Утверждение n: все островитяне знают, что утверждение n-1 истинно.
...
Гипотеза colog'а.
Пусть один островитянин на одном острове видит N голубоглазых, а другой островитянин на другом острове видит K голубоглазых, причем K>N. Тогда если первый островитянин знает какое-то из вышеприведенных утверждений, то это же утверждение знает и другой. Ведь очевидно, правда? Но я так и не сумел это строго доказать. Может быть, кто-нибудь поможет мне?
Предположение индукции.
Островитянин, видящий ровно n голубоглазых, знает все утверждения с номером не больше n и не знает остальные.
База: проверим предположение при n=0. Островитянин, видящий ровно 0 голубоглазых, знает все утверждения с номером не больше нуля (то есть ни одно) и не знает остальные (то есть все). Это очевидно.
Шаг индукции. Пусть предположение уже доказано для n=N. Пусть островитянин видит N+1 голубоглазых. Он думает, что сам а) кареглазый или б) голубоглазый.
а) Его соотечественники видят каждый по N голубоглазых. Следовательно, по предположению индукции они знают утверждения с номером не больше N не знают остальные.
б) Они видят каждый по N+1 голубоглазых. По гипотезе colog'a они знают все те утверждения, которые знали бы, если бы видели только N голубоглазых, и может быть, какие-то еще.
Так как у нашего островитянина нет сопособа определить, какой из двух вариантов соответствует истине, он может принять за истину только те утверждения, которые истинны в обоих вариантах.
Итак, он точно знает, что в обоих вариантах соотечественники знают утверждения от 1 до N. Сам он тоже знает эти утверждения (что следует из гипотезы colog'a). Значит, он знает утверждения от 1 до N+1. Знает ли он остальные утверждения? Нет, потому что для этого должна быть уверенность, что и в варианте а), и в варианте б) островитяне знают соответствующее утверждение с номером на 1 меньше. В варианте б) островитяне еще, может быть, что-то знают, но в варианте а) они совершенно определенно не знают нужного утверждения. Таким образом, наш островитянин знает утверждения с номером не больше N+1 и не знает остальные. Что и требовалось доказать.
Ну вот, осталось доказать только гипотезу colog'а, и доказательство будет закончено.
Quark Fusion:
ОтветитьУдалить>colog, не обязательно рассматривать случаи с Г=2 и ниже, что вас ограничивает идти до начала ряда натуральных чисел? Почему вы не рассматриваете что думает вымышленный Г в случае Г=0? :) А в случае Г=-1? (пусть это будет вооброжаемый Г, которого воображают все сразу и думают, что он на самом деле есть, хотя его никто и не видит)
Вполне можно рассмотреть воображаемого Г в случае Г=0. Каждый кареглазый воображает, что он сам голубоглазый или кареглазый. Вот вам и воображаемый Г в случае Г=0. Случай Г=-1, очевидно, невозможен логически.
>Мы тут думаем по принципу если алгоритм верен для Х и верен для Х+1, то мы доказываем непрерывность возрастания функции на интервале [X;+∞), что означает, что алгоритм будет верен для всех Х+А, где А>0 — для А<0 мы ничего не доказываем и не рассматриваем эти случаи, как выходящие за область определения. Нас вроде никто не ограничивает принимать Х=1.
Совершенно верно. Я приводил примеры с малым числом островитян только лишь для того, чтобы наглядно показать, как постепенно возрастает роль глубоко вложенных представлений. При единственном островитянине таких представлений нет, при двоих они очевидны, а вот при троих уже появляется довольно сложная и интересная диаграмма. Если попробовать нарисовать ее для Г=111, то высказывание туриста отразится на километровом расстоянии от начала диаграммы, поскольку с каждым новым островитянином диаграмма увеличивается вдвое.
У доказательство Ильи есть достоинство - оно изящно избегает всех этих заумных мыслей о мыслях, но это также и недостаток: не видно, как протекает реальная мыслительная деятельность островитян и создается иллюзия запуска волшебного таймера. Я, так сказать, снял с черного ящика крышку и показал, как в нем крутятся шестеренки.
Quark Fusion:
ОтветитьУдалитьХотя да, случай Г=0 тоже невозможен логически, но только потому, что турист объявил Г>0. А до приезда туриста такая ситуация вполне была возможной на достаточно глубоких уровнях вложенности представлений.
Илья Весенний комментирует...
ОтветитьУдалить[...]
Это понятное соображение, но оно ошибочное. Дело в том, что никто не сомневается, что все знают, что Г на острове есть. Но все ли уверены, что каждый уверен, что все знают, что Г на острове есть?
Это совсем другой вопрос! И именно на него ответил турист.
НЕТ! Все уже были в этом уверены! Вот ход рассуждений:
Я вижу х Г, если я Г, то я вижу меньше Г, чем если бы не был Г. Предположим что я Г. Тогда другие Г будут думать также, так как видят столько же Г. Я вижу, что Г существуют — они также это видят. Предположим, что я не Г, тогда Г будут видеть на 1 Г меньше, чем я. Поскольку я вижу более 1 Г, то они будут видеть более 0 Г, а это значит, что Г более нуля и они существуют.
Тут не надо продолжать до случая Г=1/Г=2 или начинать с этого случая.
По ММИ можно доказать, что это верно для любого большего числа Г. А база индукции верна для Г=3.
Илья Весенний комментирует...
[...]
Это не надо доказывать, так как это часть условия.
Островитяне не могут догадаться, что все думают о том, сколько именно на острове Г, а если они не думают, то все рассуждения становятся не верны.
Островитяне понимают, что мысль "значит это я Г?" может прийти островитянину только в случае Г=1, а это не так и они знают это. Подсчитывать точное количество Г им не нужно — достаточно знать, что Г>2 — это даст всем знание о том, что Г>1.
В общем, давайте докажите мне, что каждый из островитян думает, что другие думают о том, какого цвета у них глаза. Ведь очевидно же, что раз их более 2, то каждый понимает, что турист не сказал о ком-то конкретном и оснований для запуска механизма таймера нет.
ОтветитьУдалитьПока вы это не докажите нельзя рассуждать "я думаю так, потому что другие так думают".
Quark Fusion: поздравляю, Вы обнаружили довольно тонкий момент, которого нет в условии, но на котором держатся все решения с отплытием.
ОтветитьУдалитьУсловие было такое: все островитяне очень умные и догадаются до всего, до чего только можно докадаться.
А в доказательстве Ильи неявно предполагается следующее: все островитяне умные, все островитяне знают, что все островитяне умные, все знают, что все знают, что все умные и так далее до бесконечности.
Я чувствовал, что это подразумевалось, и даже не обратил внимание, что в условии этого не было сказано явно.
сolog, я вас не понял — информация о том, что они все умные и знают, что все на острове умные хоть и имеет решающее значение, но её всё равно не достаточно, чтобы начать отсчёт.
ОтветитьУдалитьПока островитяне не будут знать, что все островитяне ищут способ определить цвет своих глаз алгоритм не будет запущен — повода на это у них нет. Вот если бы турист им намекнул (а в условие было сказано, что они мнят себя самыми-самыми умными), что они не знают, что они на самом-то деле должны знать сколько островитян какого цвета на острове, то вот это бы заставило их подумать до чего такого они не додумались, чтобы узнать цвет своих глаз, причём все одновременно — вот тут был бы и повод и точка отсчёта, если предположить, что все они одинаково думают.
Quark Fusion: вполне достаточно. Попробуйте сами нарисовать диаграммы вложенных мыслей (сначала для острова с Г=2 и К=0, потом для острова с Г=3 и К=0), и снизойдет на Вас озарение. =) Сообщение туриста не просто запускает таймер и не просто создает точку отсчета, а действительно содержит информацию, только она так глубоко запутана в этих знает, что знает, что знает, что пока не распутаете самостоятельно несколько совсем простых случаев и случай посложнее с Г=3 и К=0, до конца все равно не поймете.
ОтветитьУдалитьQuark Fusion: и, разумеется, островитяне не думают одинаково - они думают одинаково хорошо. Одни островитяне могут воспользоваться доказательством по индукции, другие - рисовать диаграммы, подобные моей, но в итоге они все равно придут к одному и тому же выводу, просто потому что ни к какому другому выводу невозможно прийти логическими рассуждениями.
ОтветитьУдалитьЕдинственный вывод, к которому можно прийти:
ОтветитьУдалитьединственный способ определить свой цвет глаз - уехать на следущий через день после того, как отсчитал кол-во отплывших паромов, равное кол-ву видимых голубоглазых и посмотрел кто уплыл на последнем.
Если бы цель была прямо противоположной (остров - ад, паром - в рай, а прямо заявлять о цвете глаз кому-либо - запрет),
то они бы с радостью все отсчитывали бы и мирно уплыли бы.
А раз цель у них прямо противоположная, то они лишь узнали КАК УЗНАТЬ свой цвет глаз.
С тем же успехом каждый знает что можно посмотреть в отражение воды, спросить третьего, одинаковый ли у него цвет глаза со вторым...
Разумеется, они могут принять фразу туриста как точку отсчета, но надо ли им оно?
P.S.
При ситуации с одним, двумя голубоглазыми и отсутствии в изначальном условии пункта о том, что каждому известно о наличии голубоглазых - им придется уехать.
Но в текущей задаче в том виде, в котором она есть - все останутся.
Анонимному:
ОтветитьУдалить>При ситуации с одним, двумя голубоглазыми и отсутствии в изначальном условии пункта о том, что каждому известно о наличии голубоглазых - им придется уехать.
Знают ли островитяне, что если бы голубоглазых было двое или только один, то они бы уехали? Конечно знают.
Пусть на острове трое голубоглазых. Но каждый из них видит только двоих голубоглазых и думает: если я кареглазый, то через день они уедут, а я останусь, ведь двое голубоглазых должны уехать через день, оставив одного кареглазого. Так думает каждый и ждет, что остальные уедут. Но когда никто не уезжает, всем становится понятно, что исходное предположение о кареглазости было ложным. И они уезжают на следующий день.
Так что дополните ваш список еще одним пунктом: уезжает один, двое или трое голубоглазых. Впрочем, я с легкостью докажу, что тогда и четверо тоже должны уехать.
------------------------------------------------
ОтветитьУдалитьБаза индукции простая - пусть на острове есть один голубоглазый и много кареглазых сектантов. Получив подсказку от туриста, голубоглазый всё понимает: раз он видит вокруг только кареглазых, а хотя бы один голубоглазый на острове есть, то это именно он. Поэтому он - единственный голубоглазый - уплывёт с острова на первом же пароме.
------------------------------------------------
Неверно, поскольку любому сектанту известно, что голубоглазых минимум 110. Соответственно, базы у индукции по прежнему нет.
Если уж начинать рассуждение по индукции, то начинать с известных данных: пусть на острове 110 голубоглазых, то...
WBR, Teop
Приходит на ум еще и такое соображение:
ОтветитьУдалитьОбозначим за Д(Г) множество тех дней, в которые будет вынужден уехать каждый Г островитянин (согласно своим способностям суждения и своим наблюдениям), а Д(К) - каждый К (согласно тем же способностям суждения, ибо они у всех одинаковы, но уже другим наблюдениям).
Ясно, что поскольку К и Г наблюдают разное кол-во Г и К вокруг себя, то Д(Г) не совпадает с Д(К).
А теперь пусть какой-нибудь островитянин подойдет к какому-либо другому и спросит: "назови мне свой набор дней", и в зависимости от ответа делает вывод о своем цвете глаз. Данный диалог, строго говоря, является допустимым, т.к. здесь обсуждаются способности суждения и даты возможного отъезда, а не цвет глаз. [Это к тому, что запрет на обсуждение цвета глаз сформулирован весьма размыто].
Тогда ВСЕ сектанты покидают остров при первой же возможности одновременно, т.е. Д(К) = Д(Г) = {1}.
--
Kirill
---
ОтветитьУдалитьТак что дополните ваш список еще одним пунктом: уезжает один, двое или трое голубоглазых. Впрочем, я с легкостью докажу, что тогда и четверо тоже должны уехать.
---
Вы не совсем поняли суть сообщения.
В первом абзаце же написано: от ММИ они получают лишь набор действий, которые необходимо выполнить для определения цвета своих глаз.
Но они же умные, они и до этого знали такой способ определить свой цвет глаз. Так же они знают другие способы: посмотреть на свое отражение в воде, спросить, равен ли цвет его глаз цвету третьего..
Никто не заставляет их отсчитывать дни, так же как и смотреться в отражение.
При 1 или 2 г и остуствии изначальной информации о наличии г - они однозанчно узнают свой цвет по действиям других.
При цели узнать свой цвет глаз и свалить - все догадаются о возможности использовать туриста как точку остчета - и все благополучно свалят.
При цели неузнать свой цвет глаз и остаться жить - ММИ лишь останется СПОСОБОМ узнать, равным просмотру своего отражения.
Сама ММИ не раскрывает цвет глаз, она лишь раскрывает порядок действий, необходимых для этого.
P.S.
Еще раз: решение через ММИ - это верное решение чисто математического аналога задачи. Но этот чисто математический аналог не является полным аналогом приведенной задачи: в нем устранили выбор желаемой цели, к которой стремятся сектанты.
Анониму:
ОтветитьУдалитьПеречитал, кажеся, понял, что вы имели в виду, но все равно не согласен. Ведь можно "спасти" и двоих голубоглазых: для этого всем нужно закрыться в отдельных хижинах и больше не выходить оттуда, кроме как для того, чтобы, узнав свой цвет глаз, уплыть с острова. Впрочем, это исключение им и не понадобится: там, в хижинах, они могут думать сколько угодно и о чем угодно, но все равно до самой смерти от голода так и не определят свой цвет глаз.
colog:
ОтветитьУдалить> Ведь можно "спасти" и двоих голубоглазых: для этого всем нужно закрыться в отдельных хижинах и больше не выходить оттуда
Хм. И чем не вариант?
Анониму:
> При цели неузнать свой цвет глаз и остаться жить - ММИ лишь останется СПОСОБОМ узнать, равным просмотру своего отражения.
Не совсем так. По условию, они "могут догадаться до всего, чего только можно догадаться", т.е. если существует допускающая индукцию мат. модель их рассуждений, то они ОБЯЗАНЫ воспользоваться индукцией из-за требований на способность суждения.
Но в отражение смотреть их никто не заставляет.
--
Kirill
Но голубоглазых-то 111. И в предыдущей записи подробно описано, как они себя ограничили: они сознательно не говорят на тему глаз, уничтожили все отражающие поверхности, добились того, что бы приезжие не говорили им опасных фраз.
ОтветитьУдалитьБудь их двое - они по логике так и сидели бы в хижинах.
Но для текущего количества они знают, что сделали все необходимое, что бы никто не смог случайно узнать свой цвет глаз.
Подсчет дней - целенаправленные действия, а не случайные. А целенаправленно никто этого делать не будет, особенно если их не заставляют.
Они знают что можно считать дни, они знают от какого момента можно считать, что бы узнать сколько их. Но будут ли они считать без приказа?
Задача плавно переходит из математических в философские... Можно подогнать ее под второе доказательство, если обязать островитян считать дни и ежедневно справляться, кто уехал, а кто остался. Своей парадоксальности она не потеряет: все равно будет казаться, что турист не сообщил новой информации.
ОтветитьУдалитьКроме этой натяжки я, кстати, насчитал еще две. Нельзя смотреть, как кто-то подходит к парому, иначе все кареглазые уедут вместе с голубоглазыми.
Третья натяжка: островитяне не просто умные, а знают, что они все умные, знают, что все знают, что все умные и так до бесконечности, иначе второе доказательство будет неприменимо.
colog, благодарю за такой подробный разбор и грамотные ответы!
ОтветитьУдалитьИ хочу для всех добавить одно замечание по поводу связи математической модели и реального мира:
если делать скучное и длинное условие с подробными формальными объяснениями "что значит очень умные", "что значит узнать цвет своих глаз", "как можно думать за других" и так далее, то задача будет по всем пунктам корректной, но её никто не станет решать! Потому что странно терять несколько часов на чтение длинного и очень занудного текста с перечислением всех возможных деталей. Более того, даже если его прочесть, то ясности не появится. Я к тому, что даже условие не будет понято. О каком решении тогда можно вести речь?
Поэтому всюду надо искать компромисс между дотошной корректностью и интересностью (краткостью и образностью). Надеюсь, мне удалось его здесь соблюсти. И я буду благодарен за подсказки, как можно было сформулировать условие короче, но добавив ещё математической сути, чтобы учесть их при написании текстов следующих задач.
Илья Весенний, не могли бы вы привести полное доказательство, предварив это полным условием задачи.
ОтветитьУдалитьМне-таки не понятно почему индукция работает...
Илья Весенний:
ОтветитьУдалить> И хочу для всех добавить одно замечание по поводу связи математической модели и реального мира:
если делать скучное и длинное условие с подробными формальными объяснениями "что значит очень умные", "что значит узнать цвет своих глаз", "как можно думать за других" и так далее, то задача будет по всем пунктам корректной, но её никто не станет решать! Потому что странно терять несколько часов на чтение длинного и очень занудного текста с перечислением всех возможных деталей. Более того, даже если его прочесть, то ясности не появится. Я к тому, что даже условие не будет понято. О каком решении тогда можно вести речь?
Без этих оговорок о сущности мышления и прочих деталаях нельзя будет применять никаких математических методов. Как я выше отмечал, эта задача - сугубо философская из разряда "кто идет в баню" (или: чья философская позиция "правильная" - Канта или Гелеля?). Любое правдоподобное рассуждение можно в некотором приближении рассматривать как "правильное". Что-то подобное тут и происходит: решение с индукцией строго говоря некорректно (я показывал выше, почему - по предмету), но оно принимается как правильное.
+ еще я привел правдоподобное док-во того, что все островитяне свалят в первый же день - и это решение тоже до какой-то степени допустимо.
Итак, если мы хотим выставить эту задачу как математическую - то да, все сомнительные моменты необходимо занудно осветить. В противном случае - "о каком решении тогда можно вести речь?" :-)
--
Kirill
alexsmail, я не понимаю, что именно Вы не понимаете, поэтому не знаю, как объяснить.
ОтветитьУдалитьПожалуйста, задайте вопросы, что Вам не ясно - я постараюсь ответить как можно подробнее.
Другой вариант - попробуйте прочитать пояснения colog и ---, они очень понятные (и картинки хорошо ставят всё на места).
Kirill, я понимаю многие из Ваших возражений, но хотел бы убедиться, что Вы понимаете мои.
Ответьте, пожалуйста, согласны ли Вы с тем, что Ваши слова «Когда иностранец произносит свое заклинание, ни у одного из островитян не появилось новых выводимых утверждений, поскольку высказывание "на острове существует Г" выводимо у КАЖДОГО островитянина» являются ошибочными?
Если да, то мы продолжим разбираться с остальными вопросами. Если нет, то предлагаю сначала закончить с этим, чтобы не путаться (и тогда или Вы убедите меня, или я Вас). И уже затем вернёмся к интересной философской составляющей подобных задачек.
Илья Весенний:
ОтветитьУдалить> Ответьте, пожалуйста, согласны ли Вы с тем, что Ваши слова «Когда иностранец произносит свое заклинание, ни у одного из островитян не появилось новых выводимых утверждений, поскольку высказывание "на острове существует Г" выводимо у КАЖДОГО островитянина&raqip; являются ошибочными?
Мммм... давайте аккуратно разбираться.
1) предложенная мной схема аксиом и правил вывода не предполагает семантическую замкнутость (т.е. можно делать суждения "на острове есть Г", но нельзя делать суждения "утверждение, что на острове есть Г, выводимо у каждого островитянина" и т.д.) Поэтому новые выводимые утверждения не появляются (и мои слова верны в этой модели).
2) Можно предложить другую модель мышления, которая позволяет описывать такие предложения ("все знают, что все знают, что на острове есть Г"). В такой модели новые выводимые утверждения действительно появляются (и мои слова ошибочны этой модели). Проблема в том, что мне такая модель незнакома [я не умею описывать семаническую замкнутость и никто ее здесь не предложил :-(]
3) Без наличия определенной мат. модели говорить в "выводимости" как получения новых истинных высказываний из других истинных высказываний по определенным правилам бессмысленно (математически). Задача становится чисто философской - тут плюрализм решений.
Я ответил на Ваш вопрос?
Увы, при какой-либо строгой формализации задача становится страшной и теряет выразительность. Тут я с Вами согласен.
P.S. Еще одну позицию по этому вопросу представляет Непейвода в книге "Прикладная логика", глава 2 "простейшие высказывания" (http://ulm.uni.udm.ru/~nnn/prilog.pdf) называет утверждения, которые можно понимать как угодно (из них, собственно, и состоит формулировка задачи), "квазивысказываниями". Любая их формализация вызывает контрпримеры.
Kirill, спасибо за пояснения.
ОтветитьУдалитьУ меня было стойкое ощущение, что семантическая замкнутость языка, на котором, грубо говоря, сформулирована задача, существенным образом ничего не портит. Например, мы вполне можем обойтись без математической индукции, просто это очень сильно удлинит и усложнит доказательство, чтобы снять некоторые возражения. Но какие-то проблемы остаются... Надо всё внимательно проверить...
Пока у меня есть надежда на существование не очень сложного и достаточно формального описания, соответствующего Вашему пункту (2), но не порождающего парадоксов (в рамках предпринимаемых действий). Именно второй пункт мне кажется интересным, потому что он красив (это важно в любой науке) и до него нелегко догадаться. Короче, он интересен. Но когда я пытаюсь записать всё формально, то сталкиваюсь с большим объёмом работы. Надо будет ещё пробовать.
Спасибо за предложенную ссылку. Будет интересно об этом ещё подумать.
Всем интересующимся могу порекомендовать ещё одну ссылку - http://en.wikipedia.org/wiki/Common_knowledge_(logic). Интересно, что в этой статье предложена данная задача и оба доказательства - надеюсь, это поможет многим разобраться в том, что я сформулировал выше недостаточно чётко.
Желаю всем весёлых и эффективных размышлений! :)
Илья Весенний:
ОтветитьУдалитьСпасибо за ссылку, она многое проясняет! C семантической замкнутостью я погорячился - она тут ни при чем (более того, она невозможна по т. Тарского http://en.wikipedia.org/wiki/Tarski's_undefinability_theorem#General_form_of_the_theorem), ведь островитянам не нужно делать суждений об истинности собственных высказываний, а нужно всего лишь судить о том, что знают другие. Common knowledge logic видимо является ответом на мой пункт (2).
Ура, победа! :-)
--
Kirill
Илья Весенний: А я всё равно не понял.
ОтветитьУдалить"If k = 2, no one will leave at the first dawn. The two blue-eyed people, seeing only one person with blue eyes, and that no one left on the 1st dawn, will leave on the second dawn."
Вот этот момент не понятен. Я ещё в первом комментарии написал, что здесь индукция не работает. Как из того, что в первый день никто не уехал, следует что оба голубоглазых уедут.
А что имеется в виду "The above example is untrue when k > 2."?
ОтветитьУдалитьПри этом дальше вывод точно такой же, как и в предыдущем абзаце...
Evgeny: добро пожаловать в Википедию, свободную энциклопедию, которую может редактировать каждый.
ОтветитьУдалитьТо есть "The above example is untrue when k > 2." - это просто неточность?
ОтветитьУдалитьEvgeny: анонимные редакторы с IP-адресами 76.112.181.206 и 12.188.150.58 с Вами бы не согласились :)
ОтветитьУдалитьEvgeny См. линк http://en.wikipedia.org/w/index.php?title=Common_knowledge_%28logic%29&oldid=333022602
ОтветитьУдалитьАнониму, все правильно по истории в данном случае легко отследить последнюю версию.
Впрочем, я уже исправил, просто убрав смущающий абзац. Можно смотреть по http://en.wikipedia.org/wiki/Common knowledge (logic)
ОтветитьУдалитьalexsmail да, спасибо. В этой версии все понятно. Я уже покопался в истории, более-менее разобрался, как там с этой статьей все складывалось :)
ОтветитьУдалитьВот как я вижу случай когда есть два голубоглазых (2 G). Без ограничения общности назовём их первый и второй.
ОтветитьУдалитьПервый не знает своего цвета глаз, но знает, что второй G. Он также знает, что есть как минимум 1 G. Поэтому его цвет глаз может быть как G, так и NOT G.
Второй не знает своего цвета глаз, но знает, что первый G. Он также знает, что есть как минимум 1 G. Поэтому его цвет глаз может быть как G, так и NOT G.
Прошёл один день.
Первый видит, что второй ещё не уехал. Это означает лишь, что второй не сумел определить свой цвет глаз. Далее мы рассуждаем, как рассуждает первый. Он думает, что второй знает цвет его глаз, но не знает свой. Второй(вложенный) также знает, что есть на острове минимум один G. Второй(вложенный) также видит, что первый(рассуждающий) не уехал, значит первый(рассуждающий) не смог определить свой цвет глаз. Второй(вложенный) думает, что первый(рассуждающий) знает цвет глаз второго(вложенного) (он G), но не знает цвет своих глаз. И что дальше????
Второй видит, что первый ещё не уехал. Это означает лишь, что первый не сумел определить свой цвет глаз. Далее мы рассуждаем, как рассуждает второй. Он думает, что первый знает цвет его глаз, но не знает свой. Первый(вложенный) также знает, что есть на острове минимум один G. Первый(вложенный) также видит, что второй(рассуждающий) не уехал, значит второй(рассуждающий) не смог определить свой цвет глаз. Первый(вложенный) думает, что второй(рассуждающий) знает цвет глаз первого(вложенного) (он G), но не знает цвет своих глаз. И что дальше????
alexsmail: вот нарисовал диаграммы, надеюсь, с ними будет понятнее.
ОтветитьУдалитьДень 0. Так сектанты думали еще задолго до приезда туриста.
День 1. Турист только что уплыл, сообщив информацию, позволившую исключить вариант КК на всех облачках. В правом варианте Первого Второй как раз исключил этот вариант, догадался, какого цвета его глаза, и скоро должен будет уехать.
День 2. Второй не уехал! Значит, правый вариант ложен, думает Первый. Значит, я кареглазый. Через час приплывет паром, и я уеду.
(Пунктирной линией перечеркнут вариант, который тоже был бы вычеркнут, если бы Первый продумывал на облачко глубже. Но вычеркивать его нет необходимости, поскольку к тому моменту, когда его можно вычеркнуть, у Первого уже есть все нужные ему выводы)
Прошу прощения, в тексте предыдущего сообщения опечатка. В день 2 Первый, разумеется, догадался, что он голубоглазый, а не кареглазый. И еще, везде Первый находится слева, Второй - справа.
ОтветитьУдалитьcolog большое спасибо за потраченные усилия!
ОтветитьУдалитьЯ все равно не понимаю. Когда первый думает о том, как думает второй...то, что я обозначил как второй(вложенный), он должен учесть, что второй(вложенный) знает цвет глаз первого. Поэтому вариант который перечеркивается на второй день, вторым(вложенный) не должен был рассматриваться с самого начала. И это приводит к схеме, которую я описал.
Получается, что сказанное американцем родило так называемое "общее знание", которое автоматом за собой тянет возникновение индукции и очищение острова от обитателей :) Мат индукция применена правильно. Первый вариант решения, что ничего не измениться становится неверным.
ОтветитьУдалитьИлья, а не попадались ли вам экономические задачки по данной тематике?
Цепочка "все знают, что" длиной 111 - это еще не так плохо. Гораздо интереснее задуматься об утверждении, где эта цепочка является минимальным континуальным вполне упорядоченным множеством. Вот тут уже есть место где свихнуться.
ОтветитьУдалитьalexsmail: Второй (настоящий) действительно знает цвет глаз Первого. А вот Вторых (вложенных первого уровня) уже двое, и они знают цвет глаз Первого каждый по-своему: один своими глазами видит, что Первый кареглазый, другой - что он глоубоглазый. То есть нельзя говорить о вложенных Вторых, как об одной личности: у них общее только имя и то, что Первый (настоящий) знает о том, что видел и слышал Второй (настоящий).
ОтветитьУдалитьТочнее, у вложенных Вторых первого уровня общее следующее:
ОтветитьУдалить1) Выглядят так, как Второго видит Первый
2) Видят то, что Первый знает о том, что видит Второй
Остальное может различаться.
Корень моего непонимания кроется тут
ОтветитьУдалитьесть нельзя говорить о вложенных Вторых, как об одной личности Я отождествляю их. Буду думать ещё, пока не понятно.
Последний комментарий от 16:06 не понял. Проблема с падежами или мне пора идти домой. :-)
alexsmail: проверил дважды, проблемы с падежами нет. Но, признаюсь, Ваше рассуждение от 25.01.10 1:25 я тоже почти не понял - слишком уж плохо приспособлен естественный язык для таких конструкций. На диаграммах рассуждать проще.
ОтветитьУдалитьcolog, хорошо, я в спокойной обстановке ещё раз посмотрю. Спасибо большое!
ОтветитьУдалитьПроблема в том, что если предположить что островитяне настолько рациональны, что вообще способны на такие рассуждения, то им не нужен турист, как катализатор данного процесса (он ничего нового не сообщил) - они и без него могут в любой момент задаться таким вопросом и провести такую же цепочку рассуждений.
ОтветитьУдалитьТаким образом задача лишается точки отсчета .
В первом шаге допущение о том что на острове один голубоглазый невозможно - его бы там просто не было УЖЕ если бы он был один на острове, соответственно все остальные варианты автоматом исключаются (в любом случае нет определенной точки отсчета N дней).
Нельзя рассматривать несуществующий остров.
Если же в условие задачи внести туриста как явный катализатор процесса (до туриста им не важно, а турист говорит что все голубоглазые скоро умрут, если не уедут) и только после этого они думают о цвете глаз. То второе решение станет верным, первое, очевидно, не верным.
Другими словами существование такого острова(условий) невозможно в принципе (или жители дураки или уже все уехали), а отсюда можно доказать все что угодно - тут два взаимоисключающих решения.
ОтветитьУдалитьС точки зрения логики это примерно как доказательство 2*2=5 (и любому другому числу одновременно) через деление на 0.
elhana:
ОтветитьУдалить>Нельзя рассматривать несуществующий остров.
А если кто-то не знает, что такой остров не существует? А если все знают, что он не существует, но кто-то думает, что кто-то может не знать?
На иллюстрации первый голубоглазый (конечно, не из нашей, а из подобной задачи, где 5 голубоглазых и 0 кареглазых) до приезда туриста вполне законно предположил на правах гипотезы существование несуществующего с нашей точки зреня острова. Первый также предположил, что второй предположит существование несуществующего с точки зрения первого, но возможно существующего с точки зрения второго, острова. И так далее, пока своими вложенными предположениями предполагаемые голубоглазые на несуществующем острове не перекрасились все в карий цвет.
И когда приехал турист, он сообщил, что отныне, как бы глубоко ни задумывался кто-либо из островитян, тот никогда не предположит, что кто-то предположит, что кто-то предположит полный остров кареглазых. Это было действительно новой информацией, запустившей цепную реакцию.
colog, остров не существует до приезда туриста независимо от того чего они знают или не знают.
ОтветитьУдалитьУ них рассуждения начнуться в момент возникновения острова/их религии запрещающей знать цвет глаз.
Учитывая что мы рассматриваем идеальных сферических человеков на острове, то думать они начинают одновременно и знают что может быть только 2 цвета глаз и начиная с этого момента мыслительного процесса независимо от комбинации цветов глаз они тупо покинут остров и не нужен им турист - соответственно решение №1 (ничего не случиться) не верно.
Чтобы решение №1 было верно, необходимо, чтобы они не могли додуматься до решения 2 (без туриста), что противоречит условию о том, что островитяне умные.
Парадокса нет.
Да и учитывать что у всех на острове может быть один цвет глаз - некорректно, противоречит условию.
ОтветитьУдалитьЕсли допустить такую возможность и все кареглазые - турист соврет, если все голубоглазые, то решение 2 это частный случай.
elhana:
ОтветитьУдалить>остров не существует до приезда туриста независимо от того чего они знают или не знают.
Какой именно остров не существует? И может быть, даже если он не существует, стоит поразмыслить, как ведут себя его жители, поскольку жители существующего острова все равно будут о нем думать, как о возможно существующем?
>Учитывая что мы рассматриваем идеальных сферических человеков на острове, то думать они начинают одновременно и знают что может быть только 2 цвета глаз и начиная с этого момента мыслительного процесса независимо от комбинации цветов глаз они тупо покинут остров и не нужен им турист
Это утверждение ложно.
>Да и учитывать что у всех на острове может быть один цвет глаз - некорректно, противоречит условию.
До приезда туриста островитяне еще не знали, что он приедет, следовательно, могли предполагать, что кто-то предполагает, что кто-то предполагает такой вариант. После сообщения, разумеется, этот вариант уже никто не рассматривал - в этом и заключается важность сообщения.
В целом проблема состоит в том, что чтобы получить выводы второго решения отталкиваясь именно от заявления туриста, а не от наблюдений островитяне должны предположить, что кто-то из них может допустить мысль о том, что все на острове имеют один цвет глаз несмотря на то, что все они видят людей и с голубыми и с карими глазами, т.е. им не нужно заявление туриста для осознания данного факта. Они же умные! )
ОтветитьУдалитьelhana:
ОтветитьУдалить>Они же умные!
Умные, но не экстрасенсы. Когда первый думает о том, что думает второй о третьем, второй-в-голове-первого знает меньше, чем настоящий второй (потому что первый не знает всего того, что знает второй) и меньше, чем настоящий первый (потому что первый знает, что второй может только догадываться о мыслях первого). Третий-в-голове-второго-в-голове-первого знает меньше, чем и первый, и второй, и третий, и даже второй-в-голове-первого. Таким образом, чем больше "матрешек" в мыслях о мыслях о мыслях, тем меньше знает самая маленькая матрешка. Я ведь уже продемонстрировал это на диаграмме в сообщении от 26.01.10 19:29.
colog, я понимаю ход рассуждения, однако ту информацию которую сообщает "турист" - "есть по крайней мере один голубоглазый" они могут также получить посмотрев по сторонам. Тогда им не нужно об этом сообщать. В таком случае данная информация не несет дополнительного значения для них. Буквально по условиям задачи там по крайней мере сотня голубоглазых и еще больше кареглазых, все об этом знают. Чем конкретно сообщение туриста отличается от собственных наблюдений??
ОтветитьУдалитьТаким образом цепочка рассуждений начнеться до прибытия туриста.
> Умные, но не экстрасенсы.
Нужно быть экстрасенсом чтобы посмотреть вокруг?? ))
elhana:
ОтветитьУдалить>Чем конкретно сообщение туриста отличается от собственных наблюдений?
Тем, что собственные наблюдения не позволяют исключить мысль одного о мысли второго о мысли третьего и так далее до мысли сотого о полностью кареглазом острове, а высказывание туриста позволяет. См. диаграмму.
---
ОтветитьУдалитьТем, что собственные наблюдения не позволяют исключить мысль одного о мысли второго о мысли третьего и так далее до мысли сотого о полностью кареглазом острове, а высказывание туриста позволяет. См. диаграмму.
---
Вот в этом и вся загвоздка задачи.
Где сказано, что они не должны учитывать информацию альтернативного источника в процессе решения?
Мысль о полностью кареглазом острове исключается каждым голубоглазым на основании того, что каждый точно знает, что каждый на острове (все 999) видит голубоглазого.
Опять скажете, что важнее то, что важно как о них самих думает мнимый сектант стодесятого уровня?
Уже слишком много неточностей\оговорок\условностей, дабы считать правильным второе решение даже при рассмотрении сферических сектантов в вакууме.
Спор будет бесконечным, ибо переубедить кого-то тут невозможно.
Правильный ответ, как поступили бы сектанты, известен только элите умов планеты - 999 мнимым сектантам. Все, кто хочь чуть менее умен, неспособен дать точный ответ, послужила ли бы такая фраза неминуемому вымиранию, или нет.
Особо настрыные могут дальше гадать, что появилось первым: курица или яйцо.
Анонимному:
ОтветитьУдалить> Где сказано, что они не должны учитывать информацию альтернативного источника в процессе решения?
Это неявно предполагается. Не зря же остров назван Беззеркальным, а религия запрещает говорить о цвете глаз. И вообще, сферическому коню в зубы не смотрят - нет у него зубов, а есть только радиус и масса. Все такие несущественные подробности нужно разрешать самостоятельно с учетом условия и сохранением математической сути задачи - парадокса общего знания.
> Мысль о полностью кареглазом острове исключается каждым голубоглазым на основании того, что каждый точно знает, что каждый на острове (все 999) видит голубоглазого.
Мысль первого уровня, без каких-либо вложенностей исключается, да, однако опять скажу, что все самое интересное происходит на уровне мыслей о мыслях. Если не хотите думать о вложенных мыслях, изучите изящное доказательство Ильи, но и не нойте, что информация о цвете глаз появляется у островитян из ниоткуда по сигналу невидимого таймера. Я уже сто раз показывал, откуда она берется.
>Спор будет бесконечным, ибо переубедить кого-то тут невозможно.
Я бы согласился с этим утверждением, если б не следующее:
>Особо настрыные могут дальше гадать, что появилось первым: курица или яйцо.
На самом деле этот спор лучше бы сравнить со спором о разрешимости кубических уравнений, в котором одна сторона никак не хочет признать, что комплексные числа существуют.
elhana, складывается ощущение, что Вы не различаете две следующие ситуации:
ОтветитьУдалить1) турист каждому островитянину на ушко индивидуально сообщил, что на острове есть хотя бы один голубоглазый,
2) турист во всеуслышанье сообщил, что на острове есть хотя бы один голубоглазый.
Если я правильно понимаю, Ваши рассуждения базируются на первом утверждении. Но в условии задачи предложено второе, поэтому следует исходить из него.
Поясню: я такой вывод сделал из следующей Вашей фразы: «я понимаю ход рассуждения, однако ту информацию которую сообщает "турист" - "есть по крайней мере один голубоглазый" они могут также получить посмотрев по сторонам». Эта фраза выдаёт, что Вы не понимаете ход рассуждения.
Сообщите, стало ли ясно теперь. Если нет, то пишите - будем разбираться.
Илья, я вижу разницу (во втором случае это становится общеизвестно, в первом нельзя с уверенностью утверждать про случаи, когда голубоглазых меньше 3-х), однако в условиях задачи не частный случай, поэтому я считаю, что при наличии на острове минимум 3-х голубоглазых любому островитянину (в том числе и одному из голубоглазых) становится очевидно, что все островитяне знают, что "на острове есть как минимум один голубоглазый и все об этом знают".
ОтветитьУдалитьЛюбой голубоглазый видит 2-х других, при этом он может сделать вывод, что каждый из них видит как минимум одного и исходя из их поведения он покинет остров.
elhana, отлично! Тогда давайте разберёмся с Вашим случаем: на острове три голубоглазых, один из них Вы. Свой цвет глаз Вы не знаете, поэтому уверены только в том, что перед Вами два голубоглазых - Андрей и Борис.
ОтветитьУдалитьВы рассматриваете следующие варианты:
а) у Вас карий цвет глаз,
б) у Вас голубой цвет глаз.
Разберём их подробно:
а) Андрей видит Вас (кареглазого) и Бориса (голубоглазого). Он рассматривает два варианта:
а1) Андрей кареглазый (тогда на острове один голубоглазый Борис, который не знает о том, есть ли на острове голубоглазые),
а2) Андрей голубоглазый (тогда на острове двое голубоглазых).
б) Андрей видит Вас (голубоглазого) и Бориса (голубоглазого).
Мы здесь обсуждаем именно случай а1. Если во всеуслышание было сказано, что голубоглазые на острове точно есть, то этот воображаемый Борис, видя перед собой двух воображаемых кареглазых, будет уверен, что у него карий цвет глаз.
Я к тому клоню, что мало сказать
«все островитяне знают, что "на острове есть как минимум один голубоглазый и все об этом знают"». Этого утверждения хватает только на случай с двумя голубоглазыми.
Правильное утверждение: на острове есть хотя бы один голубоглазый, при этом каждый знает, что любой знает, что все знают, что каждый знает ... (111 раз) ... что все об этом знают.
Его нам хватает, чтобы честно доказать по индукции, что на 111-ый день все голубоглазые уедут. И именно это утверждение подарил американец, заявив во всеуслышание, что видел голубоглазых.
elhana, рад, что я не одинок в своём не понимании. :-)
ОтветитьУдалитьcolog, Когда первый думает о том, что думает второй о третьем, второй-в-голове-первого знает меньше, чем настоящий второй (потому что первый не знает всего того, что знает второй) и меньше, чем настоящий первый (потому что первый знает, что второй может только догадываться о мыслях первого). Третий-в-голове-второго-в-голове-первого знает меньше, чем и первый, и второй, и третий, и даже второй-в-голове-первого. Таким образом, чем больше "матрешек" в мыслях о мыслях о мыслях, тем меньше знает самая маленькая матрешка. Вот этот момент мне честно не понятен. Я отождествляют второго-в-голове-первого со вторым. Не понимаю, почему это не верно.
Приведу пример. Я допустим считаю, что Пи равно трём. На само значения Пи это не влияет ни как. Пи не равно трём, чтобы я об этом не думал.
Илья Весенний, последний ваши пост очень хорошие. Но с ним у меня та же проблема, что и раньше. А именно, случай a1 отсекается ещё на этапе рассуждения до того как учитывается информация сообщённая туристом.
alexsmail,
ОтветитьУдалить> Я отождествляют второго-в-голове-первого со вторым.
Это неверно. Например, представим, что загадано некоторое число от 1 до 100. Но при этом я знаю (подсмотрел), что это число - 42, а Вы - нет. Причём, Вы даже не знаете, что я подсмотрел. Я просто назову это число и угадаю с первого раза.
Теперь с Вашей стороны. Вы можете представить меня, угадывающего число. Но Вы ведь не знаете, что я знаю, что это число - 42! Поэтому и "я-в-Вашей-голове" будет долго и мучительно угадывать число от 1 до 100. А настоящий "я" сразу угадает => эти "я" разные :)
alexsmail:
ОтветитьУдалить7vies в общем-то правильно сказал, прокомментирую лишь ситуацию на острове.
Представьте себе остров, где Г=100 и К=0. Первый видит 99 Г, второй тоже видит 99 Г. Но если бы первый был кареглазым (а первый допускает такую возможность), второй видел бы только 98 Г. Поэтому второй-в-голове-первого видит либо 98 Г, либо 99 Г.
Можно было бы сказать, что второй-в-голове первого знает столько же, сколько натоящий второй, но первый рассматривает двух противоречащих друг другу параллельных вторых (один видит 98 Г, другой - 99 Г).
С другой стороны, можно сказать, что первый рассматривает единого второго, которому известно только то, в чем сходятся оба вторых-в-голове-первого, то есть "на острове не менее 98 Г". То есть этот единый второй-в-голове-первого знает меньше, чем и настоящий первый, и настоящий второй. В любом случае, представление первого о втором совсем не такое ясное, как сам второй.
Если первый представит, как настоящий второй представляет третьего, то в его голове это будут проделывать два параллельных вторых, каждый из которых породит двух параллельных третьих. Итого получится четверо третьих, "спорящих" друг с другом о цвете глаз первого и второго и "соглашающихся" в одном: на острове есть не менее 97 Г.
Если продолжить это рассуждение, мы доберемся до 2^99 сотых, соглашающихся только на одном абсурдно очевидном утверждении: на острове есть не менее 0 Г. Так было до приезда туриста. А после любые воображаемые островитяне будут "соглашаться" с тем, что на острове есть не менее 1 Г.
К сожалению, не могу выделить достаточно времени, чтобы над всем этим как следует поразмыслить, поэтому отвечу лишь 7vies.
ОтветитьУдалитьКак известно вероятность априори зависит от располагаемой информации. Знаете анекдот на это тему?
У блондинки спрашивают какая вероятность выйти на улицу и встретить там динозавра? Она отвечает 1/2 - или встречу или не встречу. :-)
Применяя ваш подход, динозавр-в-голове-блондинке действительно имеет вероятность быть встреченным её 1/2, так как она ничего о них не знает. Но это никак не отражается на "настоящей" вероятности, которое находится где-то между нулём и эпсилон.
Возвращаясь к книге Дугласа Адамса «Путеводитель для путешествующих автостопом по галактике», точнее к угадыванию числа 42 из ста. :-)
ОтветитьУдалитьТо, что я в своей голове перебирают меньше 100! вариантов вашего угадывания числа (лень делать более точную оценку, это ограничение сверху), никак не влияет на то, что вы угадали это с одной попытки. Чтобы я о вас не думал, на поведение вас-настоящего это отразится не может.
Секунду, это ровно то, что ВЫ говорите МНЕ.
ОтветитьУдалитьПрочитаю комментарий colog позже.
ОтветитьУдалитьalexsmail, мой комментарий относился к высказанному Вами заблуждению "Я отождествляют второго-в-голове-первого со вторым", и я попытался наглядно показать, что это не так: предсказания поведения для них различны.
ОтветитьУдалить> Применяя ваш подход, динозавр-в-голове-блондинке действительно имеет вероятность быть встреченным её 1/2, так как она ничего о них не знает.
Вы как-то неправильно применяете "мой подход" :) Если напишете подробнее ход Ваших рассуждений, то попробуем найти ошибку.
Вообще, утверждение "Как известно вероятность априори зависит от располагаемой информации" мне непонятно. Вероятность может зависеть только от событий, события - от действий человека, а вот действия человека уже могу зависить от информации.
Аналогично, мои действия, конечно, не зависят от мыслей других людей, но они зависят от моих мыслей. Для упрощения можно обозначить это так: мои действия <- мои мысли. Тогда дальше можно нарисовать такую цепочку:
мои действия <- мои мысли <- наблюдаемые события <- действия других людей <- мысли других людей
Таким образом, мои действия могут быть связаны с Вашими мыслями.
Утверждение "Чтобы я о вас не думал, на поведение вас-настоящего это отразится не может" верно только до тех пор, пока отсутствует связь "действия других людей <- мысли других людей". Если вы будете выражать свои мысли действием, они смогут отразиться на меня настоящего.
Исходная задача построена именно таким образом, чтобы определить все звенья в этой цепочке.
мои действия <- мои мысли: Житель острова, узнавший цвет своих глаз, уезжает
мои мысли <- наблюдаемые события: Все островитяне очень умные, поэтому они догадаются до всего.
наблюдаемые события <- действия других людей: Островитяне легко могут видеть друг друга.
действия других людей <- мысли других людей: Житель острова, узнавший цвет своих глаз, уезжает.
Если разорвать любое звено в этой цепочке - пропадёт и эффект связи. Вы рассматриваете частные случаи, когда отсутствует одно из звенен, но это не относится к исходной задаче, где аккуратно построена вся цепочка.
М-да, что-то у меня с "русским языка" тяжко сегодня :)
ОтветитьУдалитьЕсли я правильно понял, то ошибка в шаге индукции заключается в следующем:
ОтветитьУдалитьКаждый голубоглазый на шаге N+1 видит N голубоглазых и (почему-то) предполагает, что он голубоглазый (ждет N дней пока свалят голубоглазые). На самом деле для каждого голубоглазого ситуация ничем не отличается от кареглазого, находящегося на шаге N (и тогда ему надо ждать N-1 день).
Соответственно, в общем случае, островитянину нет смысла сваливать с острова ведь он не знает то ли он голубоглазый на шаге N+1, то ли кареглазый на шаге N.
Уважаемый аноним, у кареглазого и голубоглазого ситуации очень отличаются: один видит вокруг себя 111 голубоглазых, а другой - 110. Поэтому они делают чуть-чуть разные выводы :)
ОтветитьУдалить7vies насчёт теории динозавра-в-голове-блондики, я имел виду Байесовскую вероятность, а не частотную
ОтветитьУдалитьЭВРИКА!!!
ОтветитьУдалитьЯ понял! Перечитал все ключевые сообщения ещё раз и те, что я пропустил. Особенно мне помогли диаграммы cologа и пост 7vies о там, как связаны мысли с действиями.
Это напоминает ситуацию начала холодной войны между СССР и США. В начале 1950-ых у США было ядерное оружие и СССР об этом знало, а у СССР не было его и США об этом знало. Когда СССР создало ядерного оружия, этого было недостаточно для ядерного сдерживания. Нужно было, что США знало об этом. Но и этого, в свою очередь недостаточно, нужно, чтобы СССР знало, что США знает об этом!
Надеюсь, я всё правильно понял?
Спасибо больше всем, кто мне помог разобраться!
Жители знают друг друга, знают общее кол-во населения и сколько вокруг с голубыми и кариеми глазами. Житель уедет на остров, только если получит строгую информацию о своём цвете глаз. Каждый житель знает, что на острое много синеглазых и кариглазых. Сам он склоняется к мысли, что у него зелёные. Кто ему запретит?
ОтветитьУдалитьТурист говорит, что есть хотя бы один с голубыми. Говорит прилюдно, слышат все. И все его игнорируют, потому что думают так:
1) Я и раньше это знал
2) Все остальные это знали и раньше
3) Все остальные как и я думают, что у них зелёные и не будут рыпаться.
Так как все думают по пункту 3, то не рыпается никто. Все живут как жили. А ваше рассуждение, извините, бред, а не индукция.
Вы говорите, что турист стал триггером. Доказательство, что нет:
Островитяне ходят по острову, заглядывают всем в глаза и смотрят, кто ещё заглядывает и к скольким заглядывают. В итоге через промежуток Х абсолютно все владеют знанием, что есть хотя бы один синий. Вот вам триггер всеобщего знания. Триггер есть, ухода нет. Это подтверждает доказательство 1, что информация, данная туристом:
А) Не несёт ничего нового
Б) Не новая по природе. Общее знание и так было.
Жаль, до этого читал блог с интересом.
В смысле, что все и так будут знать, что все знают без туриста. Ошибка у вас была, а не в википедии.
ОтветитьУдалитьУважаемый аноним, в первом пункте условия чётко сказано, что все островитяне знают, что на острове бывают только голубоглазые и кареглазые. Поэтому аргументы про зеленоглазых относятся не к этой задаче, а к какой-то другой, верно?
ОтветитьУдалитьИлья, мне кажется, я поняла задачку, но остался один момент, который гложет уже несколько дней
ОтветитьУдалитьПочему вы с такой точностью указали в задаче количество не только голубоглазых, но и кареглазых?
С голубоглазыми понятно, это нужно, чтобы понять, на какой день сваливать. А с кареглазыми что-то не стыкуется.
Юлия А, во-первых, поздравляю и Вас тоже с победой над этой задачкой! Скоро будет её продолжение, где можно будет убедиться в правильности своего понимания :)
ОтветитьУдалитьА точное количество кареглазых, конечно, не необходимо. Но такая большая разница в их количествах делает рассуждения нагляднее, поэтому мне ближе именно эта формулировка задачи.
Если думать о сотне голубоглазых и сотне кареглазых, например, то ситуация радикально не изменится. Чуть труднее будет всё представить, но это очень индивидуально всегда :)
Ну то есть если сформулировать задачу с N голубоглазых и M кареглазых, то это тоже самое? А то меня не покидало чувство, что это неспроста..
ОтветитьУдалитьКажется, эта задача, некая вариация мысленного эксперимента шредингера с котом.
Только тут целый остров таких котят.
Простите за резкие слова, погорячился.
ОтветитьУдалитьСлова туриста ничего не меняют, так как мыслительная деятельность островитян логична и они не начнут панически ожидать, кто же пойдёт к парому, так как знают, что голубоглазых много, но никто на острове не знает цвет своих глаз. Если никто не знает цвет своих глаз, то никакого триггера не будет.
Даже если на острове два кареглазых и два голубоглазых. У всех и так есть общее знание: "ПО МЕНЬШЕЙ МЕРЕ ОДИН - ГОЛУБОГЛАЗЫЙ", у всех есть ещё одно знание: "ВСЕ МЫ ДРУГ ДРУГА ВИДЕЛИ И СЧИТАЛИ. ВСЕ ЗНАЮТ, ЧТО ПО МЕНЬШЕЙ МЕРЕ ОДИН ГОЛУБОГЛАЗЫЙ ЕСТЬ. ТАК КАК НИКТО ЛИЧНО НЕ В КУРСЕ О ЦВЕТЕ СВОИХ ГЛАЗ, ТО ЖИВЁМ КАК ЖИЛИ, РЕЛИГИЯ ПОЗВОЛЯЕТ".
Задача абсолютно некорректная. Чтобы подвести её к решению №2, нужно принять ряд аксиом и теорем с точным указаниям алгоритма мышления островитян и их психологии.
И да, я заявляю: всеобщее знание ничуть не отличается от единичного (на ушко) в данном случае. Задачу стоит рассматривать через призму информации. Если информации в локации не прибавилось, то жизнь не изменится. Повторюсь, так называемое всеобщее знание уже есть и ничего не меняет. Потому, что люди думают за себя, а поступки совершают на основании того, как себя ведут другие. Если никто не пошёл на паром, ЭТО ЗНАЧИТ ВСЕГО ЛИШЬ ТО, что ГОЛУБОГЛАЗЫЙ НА ОСТРОВЕ НЕ ОДИН, ЧТО И ТАК БЫЛО ЯСНО. А если голубоглазый не один, то нельзя, повторюсь, нельзя сделать никаких выводов ни в локальном, ни в глобальном масштабе. Вы за уши притягиваете аномальную рекурсию знания о знании о знании и т.д. Это не естественно. Это тупиковая ветвь, которая отсеивается логическим доводом: "я не знаю, какие у меня глаза, остальные тоже не знают, какие у них, голубоглазых много, однозначного решения нет."
Если вы не согласны, будем разбираться по мельчайшим пунктам с постоянной конкретизацией. И вот первый довод, который вам нужно опровергнуть: всеобщее знание уже было. Доказательство: каждый видел, что другой видел всех.
Вывод: все знали, что на острове по меньшей мере 110 голубоглазых. И все знали, что все знали, раз уж вам нравится рекурсия.
А вот несколько моих аксиом:
1) Островитяне не хотят в ад и будут выбирать алгоритм максимального уклонения от попадания туда. Иными словами, пока кто-то 100% не заявит цвет их глаз или 100% его можно будет определить без применения психологии, никто не сдвинется с места.
2) Для того, чтобы изменить ситуацию на острове, нужна новая информация, которую каждый не мог получить до этого. Информация всеобщая, что на острове не менее 50 голубоглазых не новая. Все знали её и все знали, что все знали.
Уважаемый аноним, вот это уже начинается конструктивный разговор!
ОтветитьУдалитьВаши возражения понятны. И Ваша позиция ясна. Поэтому давайте разберём конкретное Ваше утверждение: «Слова туриста ничего не меняют [пропущено мною] Даже если на острове два кареглазых и два голубоглазых».
1. Подтвердите, пожалуйста, что я правильно его процитировал. Если Вы подразумевали другой смысл, то поясните, какой.
2. Итак, есть два голубоглазых и очень умных человека - Вы и я. И есть ещё двое кареглазых. Вы видите одного голубоглазого - меня, я тоже одного - Вас. Всё верно?
3. Как могу рассуждать я? У меня есть два варианта: или цвет моих глаз голубой, или - карий. Правильно?
4. Если да, то я разберу обе версии, потому что по условию я могу догадаться до всего, до чего догадаться можно (другими словами, я не имею права лениться в таких вопросах).
5. Предположу, что у меня карие глаза. Тогда на острове будет ровно один голубоглазый (Вы) и ещё трое кареглазых (я и ещё двое). И если это правда, то после заявления туриста Вы отправитесь на паром (потому что в этой картине мира Вы видите только кареглазых, что неизбежно наведёт Вас на однозначный вывод, что цвет Ваших глаз голубой). Правильно?
6. А если в первый день Вы на паром не отправились, значит у Вас недостаточно сведений, чтобы уехать. Это значит, что Вы увидели рядом голубоглазого. Но кого? Только меня, больше некого. Справедливо?
7. Другими словами, или Вы уезжаете на первый день, тогда я пойму, что я кареглазый. Или Вы не уезжаете на первый день. Тогда я пойму, что я голубоглазый. И уеду на второй.
8. И Вы тоже уедете, потому что по условию задачи догадаетесь до всего, до чего можно догадаться. Поэтому Вы проведёте те же рассуждения, что я выше изложил.
Я специально пронумеровал абзацы, чтобы Вы могли конкретно указать номер строки, с которой начинается ошибка. Тогда или Вы меня убедите, что я заблуждаюсь в корректности этого рассуждения, или я смогу убедить Вас в обратном. Пожалуйста, напишите номер абзаца и суть возражения. Тогда мы сможем во всём разобраться. Жду Вашего ответа.
Огромное спасибо за ответ, дальше сам продолжу для 2*3. У Вас и вашей жены голубые глаза. Если у меня серые, то вы за день поймёте всё (ваше доказательство). Если прошёл день, а вы не двигаетесь, значит голубоглазых не два, а три! И к сожалению, третий это я. Я ухожу. Прихожу к парому и вижу, что пришёл не один, а все голубоглазые, ибо они тоже выявили себя. Итого на второй день уйдут все голубоглазые. Так? Можно по одному увеличивать кол-во и применять тот же метод. Моя ошибка в утверждении, что информации новой в локацию не добавилось. Добавилось. И это именно триггер, который не сработает в обычное время, так как последний голубоглазый может думать, что он кареглазый. Остаётся лишь формализовать эту добавленную информацию, ведь по началу кажется, что она и так имеется.
ОтветитьУдалитьЗадачу о конвертах решил сразу, совпадает с вашим ответом.
Ещё раз приношу искренние извинения.
Berserker, поздравляю, Вы почти разобрались с весьма непростой задачей!
ОтветитьУдалитьОдна тонкость: трое голубоглазых уедут на третий день, а не на второй. Как мы выше поняли, двое уезжают на второй день. Соответственно, если третий голубоглазый видит, что двое не уехали на второй день, то он делает вывод, что они видят ещё одного - его. И тогда они все втроём покидают остров на третье сутки.
Юлия А, да, Вы всё верно понимаете - модифицировать условие можно в очень широких пределах. Аналогию с котом я не очень понимаю, но предлагаю прочитать о парадоксе неожиданной казни - он близок к этой задачке :)
Аналогия с котом, конечно, не прямая...
ОтветитьУдалитьНо я вижу это так: до тех пор, пока ящик закрыт (иностранец молчит), мы ничего не можем сказать о том, жив ли кот или нет (какой у меня цвет глаз).
Открывая ящик (сообщая информацию), иностранец вроде бы не убивает/спасает кота (не сообщает ничего нового), но кот становится мертвым/живым (все уезжают с острова).
Мне один знакомый рассказал эту задачу много лет назад. Правда, была небольшая разница. Там быть голубоглазым считалось очень позорно, и островитянин, узнав, что он голубоглазый, совершал самоубийство. Но если он узнавал, что он кареглазый, никаких последствий это не влекло.
ОтветитьУдалитьЯ решил!
Юлия А, теперь сходство вижу :)
ОтветитьУдалитьВиктор, если кареглазые не боятся знать цвет своих глаз, то пропадает вторая половина задачи (о том, что все они тоже догадаются уехать). Но от этого заметно проще решить задачку не становится. Спасибо за модификацию!
Добрый день!
ОтветитьУдалитьМожет я немного припозднился со своим комментарием, но все ж выскажу точку зрения.
Никто не уедет, хотя и метод доказателься по индукции верен.
Не уедет никто потому, что островитяне (по условию) могут догадаться до чего угодно. Раз так, они (коллективно) должны рассуждать следующим образом.
1) Если я (так же как и все) начну рассуждать о том, какого цвета у меня глаза, то смогу ли я это узнать?
2) Да смогу, т.к. (далее ответ №2 при помощи индукции).
3) Если я узнаю какого цвета у меня глаза, то я поеду в АД, так же как и все мои со-островитяне, причем это случится на 111 или 112 день.
4) Хочу ли я уехать с этого острова, начав рассуждать о том, какого цвета мои глаза?
5) Нет не хочу, так же как и не хотят все мои со-островитяне, иначе бы мы уже начали об этом думать и уехали бы с острова.
6) Значит, после слов туриста мне не надо начинать выяснять какого цвета мои глаза.
Я исхожу из следующей постановки задачи:
ОтветитьУдалить1. Островитяне допускают, что количество Г или К может быть равно нулю (иначе смысла нет), даже если сейчас они видят что оба числа не нулевые, они допускают, что теоретически такое может быть.
2. Островитяне не располагают никакой информацей кроме того, что на острове могут быть только Г и К, цветов глаз других туристов, того, что каждый день в 17:00 одновременно все, кто способен однозначно вычислить свой цвет глаз, уезжают на пароме. То есть вероятность узнать цвет глаз случайно = 0%
Занумеруем для нашего понимания всех людей от одного до много, и допустим, что первые пять - голубоглазые. Пусть N > 10.
Тогда рассмотрим рекурсивные мысли первого (сори за подчерквания, не знаю как еще сделать отступ)
До туриста
1. Первый видит четырех, значит всего Г либо 4 либо 5
2. Если Г всего пять, то все остальные мыслят также, и придут к такому же выводу
3. Если Г всего четыре, то как мыслит второй?
_a. Второй видит троих, значит всего Г либо 3 либо 4
_b. Если Г - четыре, то все мыслят также и придут к такому же выводу
_c. Если Г - три, то как мыслит третий?
__i. Третий видит двоих, значит всего Г либо 2 либо 3
__ii. Если Г - три, то все мыслят также и придут к такому же выводу
__iii. Если Г - два, то как думает четвертый?
___1) Четвертый видит одного Г, значит всего Г либо один, либо 2
___2) Если Г - два, то они оба думают одинаково и примут одинаковое решене
___3) Если Г только один, только пятый, то как он мыслит?
____a) Пятый не видит ни одного Г, значит их либо ноль либо один
____b) У пятого нет никакой информации чтобы понять, ноль их или один.
____c) Пятый никогда не уезжает с острова
___4) Четверый никогда не уезжает с острова
__iv. Третий никогда не уезжает с острова
_d. Второй никогда не уезжает с острова
4. Первый никогда не уезжает с острова
После туриста
1. Первый видит четырех, значит всего Г либо 4 либо 5
2. Если Г всего пять, то все остальные мыслят также, и придут к такому же выводу
3. Если Г всего четыре, то как мыслит второй?
_a. Второй видит троих, значит всего Г либо 3 либо 4
_b. Если Г - четыре, то все мыслят также и придут к такому же выводу
_c. Если Г - три, то как мыслит третий?
__i. Третий видит двоих, значит всего Г либо 2 либо 3
__ii. Если Г - три, то все мыслят также и придут к такому же выводу
__iii. Если Г - два, то как думает четвертый?
___1) Четвертый видит одного Г, значит всего Г либо один, либо 2
___2) Если Г - два, то они оба думают одинаково и примут одинаковое решене
___3) Если Г только один, только пятый, то как он мыслит?
____a) Пятый не видит ни одного Г, но знает, что один есть
____b) Пятый уезжает в первый день.
___4) Значит, если пятый не уехал в первый день, значит Г два, а значит четвертый - Г, и он уезжает во второй день, как и пятый, так как он примет такое же решение
__iv. Если четвертый с пятым не уехали во второй день, значит Г три, а значит третий - Г, и он уезжает в третий день, как и четвертый с пятым, которые мыслят также
_d. Если 3-5 не уехали на третий день, значит всего Г - четыре, и значит второй - Г, и ему надо уехать в четвретый день, как и 3-5, которые мыслят также
4. Если 2-5 не уехали на четвертый день, то короче вы поняли
Каждый голубоглазый сектант видит к-1 голубоглазых сектантов, а каждый кареглазый - ровно к.
ОтветитьУдалитьпоэтому на (к-1)ый день все голубоглазые встанут и пойдут на паром, а вслед за ними потянутся и кареглазые. Но раскрытие информации о цвете глаз произойдет именно в момент когда все видящие на одного меньше встанут и пойдут.
Если же они не встанут и не пойдут, то раскрытия информации о свете собственных глаз не произойдет.
ОтветитьУдалитьОднако, на следующий день, после того как голубоглазые не поедут - встанут и пойдут на паром все кареглазые.
ОтветитьУдалитьПравда, с неверным предположением, что они голубоглазы. Увидев цвет глаз собравшихся уезжать - проклянут себя за излишнюю сообразительность и все-таки уедут, но уже как кареглазые, а голубоглазые поедут следующим паромом.
Оговорка о том, что, если и кареглазые не двинутся с места, то и информации не добавтся и в своем цвете глаз не будет уверен никто - остается в силе.
Если я правильно помню, оператор "знания" уводит нас в область модальной логики. И одна из её аксиом (The positive introspection axiom) говорит, что: KF => KKF (K - знание, F - факт).
ОтветитьУдалитьМне кажется, что диаграмма вложенных мыслей от colog не верна.
Начинается всё же на тойке:
ОтветитьУдалить0) Если голубоглазых 3-ое, то все знают, что голубоглазые существуют (их количество больше 0-я). Соответственно, все знают, что в первый день никто к парому не придёт.
1) В первый день к парому придёт тот кто не знал, что голубоглазые существуют - никто.
2) Во второй день к парому придёт тот кто знает одного голубоглазого, который не пришёл в первый день. Но в первый день никто и не собирался приходить - смотри пункт 0.
Всё - рекурсии нет.
sans17, я не совсем понимаю Ваше возражение.
ОтветитьУдалитьВы пишете: «Если голубоглазых 3-ое, то все знают, что голубоглазые существуют», но это утверждение неверно. Дело в том, что воображаемые люди (а именно о рассуждениях воображаемых людей идёт речь) не видят всей картины физического мира.
Извините, как это не верно?
ОтветитьУдалить0) Я голубоглазый (или кареглазый).
1) Я беру любого товарища на острове, мы - проходим по всем домам, и обязательно увидим хотя бы одного голубоглазого.
2) Из этого я делаю вывод, что этот товарищ знает о существовании голубоглазых.
Где ошибка?
Ошибка во вложенных воображениях, что если на первом уровне воображения мы рассматриваем 2 варианта, то и на втором тоже должно быть два варианта (второй воображающий знает мой настоящий цвет - даже если я его не знаю). Что бы не произошло на втором уровне воображения, на первом уровне воображения все трое знают о существовании голубоглазых (у всех троих должен стоять восклицательный знак (!))
ОтветитьУдалитьКак раз таки наоборот - коль все логичны до безобразия, то воображаемые люди должны обладать всей картиной мира на которую способны реальные люди. А вы их загоняете всё глубже в воображаемый мир, где остаётся всё меньше реальности (воображающего на первом уровне лишили знания о моём цвете глаз - подменили это знание моей догадкой).
ОтветитьУдалитьБолее точная рекурсия для трёх голубоглазых будет следующая:
ОтветитьУдалить1) в первый день придут те кто не знает что голубоглазые существуют - таких нет, и все об этом знают;
2) во второй день придут те (1) кто знает ровно одного голубоглазого (2) о котором есть подозрение, что он не знает, что голубоглазые существуют - 2 не существует, никто не придёт;
3) в третий день придут те (1) кто знает ровно двух голубоглазых, про которых (2 - каждого из них) есть подозрение, что они знают только одного голубоглазого (3) о котором есть подозрение, что он не знает, что голубоглазые существуют - 3 не существует, никто не придёт.
Где ошибка?
---- sans17
sans17, я правильно понял, что Вы не можете найти ошибку в доказательстве методом математической индукции, которое описано в заметке?
ОтветитьУдалитьТеперь детально:
> Извините, как это не верно?
Уже ответил выше: "в рассуждении участвуют воображаемые люди, которые не всё видят".
> 2) Из этого я делаю вывод, что этот товарищ знает о существовании голубоглазых.
Где ошибка?
Тут нет ошибки. Но мы говорим не про физического товарища, а про вымышленного, который может предполагать, но не может знать некоторые вещи.
> воображаемые люди должны обладать всей картиной мира на которую способны реальные люди
Вы можете объяснить, почему они это должны? Речь не об эмоциональном, а о логическом объяснении.
> Более точная рекурсия для трёх голубоглазых будет следующая
Рекурсия? Она тут при чём?
И что значит "более точная"? Бывает верное описание событий, бывает ошибочное, а бывает такое, истинность которого невозможно оценить.
Уговорили :), с рекурсией я ошибся.
ОтветитьУдалитьНо тогда я вижу два варианта, зависящие от общего знания людей на острове (все знают, что все об этом знают - в школе об этов всем рассказывают):
1) Общее знание - "существуют только голубоглазые и кареглазые люди": по рекурсии изойдут голубоглазые, на следующий день уйдут кареглазые (если кареглазых меньше, уйдут в обратном порядке).
2) Общее знание - "у глаз есть цвет": по рекурсии изойдут голубоглазые, все кареглазые останутся (каждый из них будет воображать себе зелёный цвет).
Второй вариант выглядит более вероятным.
Н-да. Убойно.
Вот.
ОтветитьУдалитьЭтот подпункт (... Они легко могут видеть друг друга и знают, что людей с другим цветом глаз на острове не может быть. ...) в №1 в условии запутывает дело. Создаётся впечатление, что одно выводитья из другого. "И" как "и следовательно".
На самом деле это два независимых факта? (Они легко могут видеть друг друга. Каждый из них знает, что людей с другим цветом глаз на острове не может быть).
Интересно также, как возникло такое знание (что других цветов нет)? :) Без обмена информацией не обошлось.
sans17, знание о том, что других цветов нет, является частью условия задачи. Так устроен обсуждаемый мир.
ОтветитьУдалитьЧто касается независимости двух утверждений, то это тоже часть условия задачи. Нигде не утверждается, что одно следует из другого. Но известно, что оба утверждения верны.
Илья, я в вас разочарован :) Первоначальный пост не содержал никакого решения, подло и изподтяжка подталкивал к придумыванию сложного и НЕПРАВИЛЬНОГО решения через матиндукцию, хотя ответ был очевиден. Ну это как если бы вы спросили сколько будет 2х2? и что-то туманно намекнули про комплексные числа (с их помощью можно "доказать", что будет 5) и про то, что кто-то счтитает как-то хитро, не дав ни "ответа", ни "решения". Это не ваш уровень :) В этом посте уже лучше, но тоже как-то слабо и неинтересно.
ОтветитьУдалитьПо поводу задачи: жители - тупые компьютеры, любой алгоритм - это переработка входной информации в выходную и для применения матиндукции вы должны были бы доказать, что на каждом шаге индукции ничего не меняется во входной информации, кроме k. Могу на пальцах показать, что ситуации с k=1 и k>1 не имеют ничего общего.
Вот вам упрощенная формулировка этой задачи: есть большое число N жителей острова. Каждый житель сегодня покончит с собой в предощущении одиночества, если будет уверен, что завтра останется 1. "Ответ": все жители покончат с собой в один день. Можно ввести какого-нибудь туриста для отвода глаз, который ничего не делает, чтобы читатели не задумывались в КАКОЙ день? Для N=1 решение очевидно. Допустим, что решение верно для k жителей, тогда оно верно для k+1 жителей, поскольку k+1 будет точно знать, что завтра останется 1. Так можно доказать все, что угодно.
Уважаемый аноним, Вы дали одинаковые комментарии в двух местах (здесь и в первой заметке об этой задаче), поэтому я отвечу только здесь.
ОтветитьУдалитьИтак, Вы утверждаете, что применение метода математической индукции здесь некорректно, но не можете чётко сказать, в каком месте ошибка, я правильно Вас понял?
Разговоры "вот я тут сам так-то неправильно сделал, поэтому получил неправильный ответ" не годятся для такого опровержения. Метод математической индукции хорошо формализован, он не является шаманством, поэтому всегда можно абсолютно чётко указать на ошибку при его применении, если она есть.
Единственный способ узнать свой цвет глаз - узнать количество Г и К. Если каждый это узнает, то се жители уплывут на Ад, и естественно такого никто не хочет и не делает.
ОтветитьУдалитьОбщее условие отезда голубоглазых по решению из ММИ - "я вижу N голубоглазых, если я
голубоглазый то нас N+1 человек, и на N+1 рейс парома все голубоглазые должны уплыть. Если я не голубоглазый, то то их N человек и они все должны уплыть N-ым рейсом парома". Тоесть каждый житель должен пересчитать остальных, и те кто насчитает N голубоглазых будут ждать N рейсов, а те кто насчитал N+1 - ждут N+1 рейсов. Роль туриста сводится к провокации подсчета жителей. Но они ведь абсолютные логики и понимают что если каждый так сделает, то всем прийдется уплыть на Ад, а потому они просто проигнорируют сообщение туриста.
В этой задаче, как и в большинстве опубликованых в этом блоге, есть возможность по своему трактовать условие и которая не позволяет дать абсолютно строгий ответ.
Мой ответ: ничего не изменится.
Нет, Илья. Я имел ввиду, что ситуация, использованная в базе индукции, и ситуация, использованная в шаге индукции - это 2 *разные* задачи. Они только выглядят схожими.
ОтветитьУдалитьУважаемый аноним, Ваш тезис понятен, но я с ним не согласен. Вы можете его обосновать? Я перечитал доказательство, но всё ещё вижу базу и шаг индукции для одной и той же задачи. Поясните, пожалуйста, почему Вы считаете, что задачи разные.
ОтветитьУдалитьlampika , Вы пишете «Но они ведь абсолютные логики и понимают что если каждый так сделает, то всем прийдется уплыть на Ад, а потому они просто проигнорируют сообщение туриста.», но это не соответствует условию задачи. Аборигены обязаны догадаться до всего, до чего можно догадаться, поэтому они не будут игнорировать какие-то факты из-за того, что не хотят уплывать.
Илья Весенний, вы подразумеваете под словами "обязаны догадаться до всего, до чего можно догадаться", вдруг вскочить и приняться всех пересчитывать, только потому что какой то американский турист сообщил им в неявной форме то что они знали и без него? И кроме того, догадаться не значит совершить действия для того чтобы догадались ДРУГИЕ.
ОтветитьУдалить"... Приятно было в этом дивном месте встретить человека с такими же голубыми глазами, как у меня" - какой факт в этой фразе может заставить 999 умных(и весьма умных, ибо даже среди людей с высшим образованием, нечасто встречаются способные применить в житейской ситуации метод индукции) людей пересчитать всех на острове? Прийти на причал, при этом даже не зная цвет своих глаз, значит сообщить остальным ихний цвет, так получается по решению.
Илья, мне понятно желание подольше растянуть дискусию по каждой своей статье, но цепляться за своеобразное понимание отдельных слов условия задачи некрасиво, тем более что вам в этом неоднократно упрекали. Догадаться - http://www.classes.ru/all-russian/russian-dictionary-Ozhegov-term-7201.htm
lampika, спасибо за интересный ответ.
ОтветитьУдалитьУ меня нет желания растягивать дискуссию. Но я готов отвечать на вопросы до тех пор, пока у они есть. Если Вам нравится Ваше нынешнее понимание этой задачи, то я, конечно, не буду ни на чём настаивать. Успехов!
Илья, я - программист (с математическим образованием), а вы, видимо, математик. Нам приходиться говорить на немного разных языках. Но, думаю, мы поймем друг друга. Задачи разные потому что, в базе индукции и на последующих шагах меняется алгоритм поведения аборигенов. То есть алгоритм поведения зависит не только от номера шага индукции, но и от других параметров. Поэтому матиндукция неприменима.
ОтветитьУдалитьКстати, у вас есть правильный ответ? Если есть, то, думаю, пора его опубликовать. Может быть, я соглашусь с вашим опровержением "доказательсва".
С уважением, Алекс.
Алекс, спасибо, что стараетесь объяснить свою позицию. Я думаю, два человека с математическим образованием друг друга поймут, если найдут для этого достаточно времени.
ОтветитьУдалитьЕсли я правильно понимаю, у Вас возражение вызывает именно тот факт, что базу мы доказали для одного голубоглазого, а у него очень специфическая ситуация (отличающаяся от двух, трёх и большего количества голубоглазых на острове).
Но в тексте заметки есть абзац, начинающийся словами "Пусть на острове есть двое голубоглазых и много кареглазых...". В этом абзаце доказана база индукции для двух голубоглазых. Ну а далее можно спокойно делать шаг от n к n+1, получив доказательство для произвольного количества голубоглазых.
Более того, можно сконструировать такое же доказательство для трёх голубоглазых (не используя ММИ) и для большего их числа. Вообще говоря, метод математической индукции нам здесь не нужен. Но без него доказательство станет необозримым.
Итого:
1) Согласны ли Вы, что мы можем проверить базу не только для одного голубоглазого, но и для двух?
2) Согласны ли Вы, что для трёх и четырёх тоже можно сконструировать обозримое доказательство?
3) Если так, то начиная с какого количества голубоглазых задача так меняется, что шаг индукции становится некорректным?
Что касается правильного ответа, то я считаю, что опубликованное решение с ММИ является верным. Если Вам интересно узнать мнение других людей, то рекомендую следующие ссылки:
1) http://www.math.ucla.edu/~tao/blue.html (если я правильно понимаю, это автор задачи),
2) http://terrytao.wordpress.com/2008/02/05/the-blue-eyed-islanders-puzzle/ (он же, тут комментариев много, но дельных мало)
Надеюсь, эти две ссылки помогут Вам выделить ключевые слова, по которым стоит искать в сети содержательные дискуссии об этой задаче.
Буду рад, если Вы меня переубедите. Но пока я не понимаю Ваше возражение. Было бы очень ценно, если бы Вы его смогли уточнить.
"Более того, можно сконструировать такое же доказательство для трёх голубоглазых (не используя ММИ) и для большего их числа."
ОтветитьУдалитьНе согласен. В случае с тремя голубоглазыми, любой человек на острове будет видеть как минимум двоих голубоглазых, что не позволит сделать однозначный вывод аналогичный случаю с одним или двумя голубоглазыми на острове.
Dima, у Вас интересное утверждение, но хотелось бы знать, на чём оно основано.
ОтветитьУдалитьГод назад в комментариях к этой заметке мы уже разбирались со случаем трёх голубоглазых и произвольного количества кареглазых.
Другими словами, существенного отличия случая с трему голубоглазыми от случаев с одним или двумя нету. Просто рассуждение становится чуть-чуть длиннее.
Илья, каюсь - грешен. Невнимательно прочитал вашу вторую заметку. Это я про "Пусть на острове есть двое голубоглазых и много кареглазых...". Объясню свою пересмотренную позицию.
ОтветитьУдалитьЭта задача сродни "парадоксу узника", которого, якобы, не смогут казнить (ссылку не даю ибо думаю, что вы знаете эту задачу). Там вся суть, что в *доказательстве* (не в условии) узнику навязывается определенный алгоритм мышления, причем, сам начальник тюрьмы отнюдь не рассуждает по этому алгоритму (если бы рассуждал и был честным, то узника не смогли бы казнить). В вашей задаче тоже фраза "аборигены могут догадаться до всего до чего можно догадаться" слишком расплывчата. Вы же математеик и знаете, что все "парадоксы" основаны на противоречивых или неполных условиях (в последнем случае дополнительные условия обычно запихиваются внутрь доказательсва, чтобы не выглядели как условия). На самом деле надо было четко расписать алгоритм рассуждения аборигенов в условии задачи. Но тогда задача была бы без подвоха и стала бы никому не интересной. Вы по приведенной ссылке указываете, что аборигены *должны* рассуждать по определенному алгоритму. Но если *должны*, то *будут*. И тогда они *действительно* все уедут с острова. Другой вопрос, что этот алгоритм вовсе не является самым умным с моей точки зрения. Но это уже другая тема. Как то так.
P.S. В первой замеке вы, думаю, специально не
привели ни доказательсва, ни ответа, так как вас часто обвиняют (вы сами об этом писали), что у вас все задачи с подвохом и это заставляет тщательно проверять доказательства. Если это так, то лучше не заморачивайтесь на эту тему, поскольку
если бы ваши простенькие задачи были *без* подвоха, то ваш блог никто не стал бы читать. Так что уйти от того, что все знают, что есть подвох вам все равно не удастся.
Алекс.
Алекс, спасибо за пояснения.
ОтветитьУдалитьБыло бы интересно узнать Ваше решение (речь о Вашем утверждении, что предложенный в заметке алгоритм действий аборигенов не является самым умным).
Илья, я считаю, что самым умным для аборигенов будет ничего не делать. Только я не писал "не является" - я писал "не кажется мне" (ну, хорошо, "не является с моей точки зрения"). Дело в том, что термин "умный" не является математическим - это понятие субъективное. Вы можете (к примеру - я не знаю вашей точки зрения) считать недавнее доказательство теоремы Ферма очень умным (а оно очень сложное - не каждый в нем разберется), а я считаю умным доказательство самого Ферма в несколько строчек (если оно, конечно, действительно существовало).
ОтветитьУдалитьЛично я считаю умным для аборигенов ничего не делать просто потому что это кажется мне очевидным. Я ненавижу слово "очевидный" - меня еще на Физтехе приучили, что ничего очевидного не бывает (даже аненкдот был на эту тему - когда преподаватель матана написал один крокодил на доске, потом сказал "отсюда с очевидночстью следует" и написал другой крокодил, задумался на полчаса и сказал "да, это действительно очевидно"). Но другого объяснения у меня нет.
Вы согласны с тем, что турист в задачу введен исскуственно для замыливания глаза? Если его выкинуть из задачи - ничего по сути не изменится? Тогда у меня у меня вопрос - в какой день все должны уехать с острова в задаче без туриста?
Все это никак не опровергает тот факт, что ваше решение задачи тоже является верным, поскольку приведенный вами алгоритм не является внутренне противоречивым.
Алекс.
Постановка задачи не годится, по-моему. Информация, которую дает турист уже есть у каждого жителя! Так что если остров появился сейчас, то они все должны уехать через 111 дней, и неважно когда там появился турист, он ни на что не влияет, как уже это было замечено.
ОтветитьУдалитьЛично мне эта задача знакома в другой постановке:
В какой-то стране есть Царь и 20 султанов, у каждого из которых по одной жене. Царь прознал о том, что многие из жен не верны своим мужьям, и решил бороться с этой проблемой самыми решительными методами, а именно:
Он посадил султанов и их жен парами в глубокие ямы таким образом, чтобы исключить возможность коммуникации между любыми ямами.
И выдвинул условие, что их не будут кормить до тех пор, пока султаны сами не убьют ВСЕХ неверных жен.
Султаны знают о похождениях всех жен, кроме своей.
Жены хотят жить.
Султаны жен своих любят и зря убивать не станут, пока не убедятся в их неверности.
Султаны умные (могут догадаться до всего, до чего можно догадаться).
Каждый вечер Король приходит, осматривает ямы и либо отпускает всех, если условие выполнено, либо оставляет всех еще на один день.
Вопрос 1 - смогут ли султаны оставить верных жен в живых и выбраться?
Вопрос 2 - если неверных было 17, то через сколько дней им удастся выбраться?
Максим