12 февр. 2010 г.

Остров Беззеркалья - два продолжения

Многие теоремы формулируются следующим образом: если выполнены такие-то условия, то будет такое-то следствие. В моём ВУЗе частенько используют следующее не очень строгое выражение - «придумать контрпримеры к теореме». Со стороны это выглядит так же странно, как присваивание в Си-подобных языках для человека, не знакомого с их синтаксисом:

x = 2*2;
x = 5;

Типичное возражение, которое я много раз слышал от таких людей: «Если на первой строчке сказано, что x равно дважды два, то утверждение во второй строке является не только ложным, но и некорректным» (а оно, оказывается, и корректно, и истинно). Просто в Си-подобных языках обычное математическое равенство записывается удвоенным знаком «равно»: «if (x==5) ...».

Аналогичное соглашение о смыслах используем и мы: отлично зная, что такое контрпример для опровержения, термином «контрпример к теореме» мы обычно называем такое построение, которое удовлетворяет всем условиям теоремы, кроме одного, но для которого не верно следствие этой теоремы. Другими словами, сочиняя контрпримеры к теоремам, мы убеждаемся, что все их условия являются необходимыми. Это полезное упражнение, позволяющее лучше понять суть теоремы.

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

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

Задача 1
Министр МСЧ России Сергей Кужугетович Шойгу узнал о чрезвычайной ситуации - об отъезде с острова Беззеркалья не очень внимательного и слишком разговорчивого туриста. Сергей Шойгу человек быстрый, умный и решительный, поэтому сразу понимает, что без его вмешательства через несколько месяцев все островитяне уплывут на пароме, как им предписывает поступить в такой ситуации религия. Поэтому он отправляется на остров.

Вопрос: что он может сделать, чтобы спасти (хотя бы некоторых) островитян от отъезда с острова?

Скорее всего, люди, решившие исходную задачу, уже всё придумали. Но иногда так бывает, что вроде бы есть иллюзия, что всё ясно, а какой-то важной детали нету. И тут на помощь приходит наш метод «качания условия задачи»: если первая задача у вас никак не решается, то предлагаю сначала вникнуть во вторую.

Задача 2
Учёные островитяне не сидели сложа руки за 5 лет до упомянутого приезда туриста на остров Беззеркалья: они смогли откопать древнюю пещеру, на стене которой было высечено предсказание от людей, живших здесь много веков назад.

Надпись гласила: «Через 5 лет после прочтения вами этой надписи посетит этот остров один болтливый тип. И скажет он вам, что среди вас есть хотя бы один голубоглазый.»

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

Вопрос: что было дальше?

Хороших вам выходных!

81 комментарий:

  1. Анонимный12.02.2010, 17:07

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

    ОтветитьУдалить
  2. Анонимный12.02.2010, 17:14

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

    ОтветитьУдалить
  3. Уважаемый первый аноним, а что поменяется в индукционных рассуждениях, если выгнать одного конкретного голубоглазого?

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

    ОтветитьУдалить
  4. Анонимный12.02.2010, 17:50

    Поменяется база индукции. На примере 2-х голубоглазых: названный уезжает в первый день, тогда второй не имеет информации о своих глазах. Тогда, в случае 3-х, третьему нет резона предполагать отъезд второго. И так далее.
    Аноним-1 :)

    ОтветитьУдалить
  5. Между прочим, без помощи Шойгу островитянам не так-то просто объединиться в группу с целью пожертвовать одним голубоглазым, но при этом не сболтнуть друг другу, как турист, ничего лишнего. Я пробовал придумать целых две формальные процедуры изгнания, но в каждой нашел недостатки, из-за которых с острова уплывает не только выбранная жертва. Первая процедура - выгнать самого старого голубоглазого, ее недостаток - если есть ровно один островитянин старше изгнанного, то он сразу догадается, что кареглазый. Вторая процедура использует генератор случайных чисел и намного сложнее, но тоже иногда дает сбой.

    ОтветитьУдалить
  6. Люди, ну что вы привязались к этой индукции? Ну не работает она тут!!!
    И как ты не крути - у этой задачи нет решения, т.к. для этого недостаточно данных.

    В условии не дано, знают ли сами аборигены точно сколько на острове человек и с какими глазами. Если знают, то они просто могут посчитаться - и все станет очевидно для каждого человека какой у него цвет глаз.
    А если они не знают, то ничего не изменится. всем и так видно что есть вокруг и кари и голубоклазые, и по условию итак известно всем, что голубоглазых больше одного, так что турист не дал НОВОЙ ИНФОРМАЦИИ.

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

    Во втором случае все также как и с непосредственно туристом - пророчество не дает новой информации, следовательно не влияет на исход.

    В задаче важно не только понять каких данных недостаточно, но также понять какие лишние.

    ОтветитьУдалить
  7. Анонимный13.02.2010, 02:26

    EvilPartisan, поддерживаю

    ОтветитьУдалить
  8. EvilPartisan, во втором пункте условия сказано: «они изначально не знают количество голубоглазых и кареглазых на острове (иначе бы они мгновенно вычислили свой цвет глаз)». И после этого Вы пишете: «В условии не дано, знают ли сами аборигены точно сколько на острове человек и с какими глазами»

    Кого Вы обманываете? Себя или других читателей комментариев? vicnaum, Вы поддерживаете такие попытки запутать людей, желающих разобраться в задаче? Будьте серьёзнее, не теряйте чужое время на ерунду!

    ОтветитьУдалить
  9. Хотя нет, вру, выгнать одного голубоглазого можно и без Шойгу - случайный островитянин должен сказать случайному голубоглазому его цвет глаз. Но вот чтобы все одинаково мыслящие островитяне не привели в исполнение эту стратегию одновременно, прогнав всех голубоглазых, им придется изобрести часы и генератор случайных чисел. С помощью этих приборов островитяне определят порядок, в котором им нужно говорить. Кстати, если попробовать доформализовать эту стратегию до конца, то придется либо сделать часы и генератор случайных чисел бесконечно точными, либо мучительно выискивать подводные камни, связанные с совпадениями случайных чисел, получением информации из молчания островитян и т. п.

    ОтветитьУдалить
  10. Владимир13.02.2010, 10:17

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

    ОтветитьУдалить
  11. По поводу острова — объясните мне, как вообще такой остров может зависеть от высказывания туриста? Ведь любое собрание всех островитян вместе запускает мысль "все знают, что все знают, сколько на острове всего островитян" (поскольку все такие умные и сразу до этого додумаются), на основании этой мысли можно принять момент её получения за точку отсчёта (до этого все додумаются, опять-таки потому, что такие умные) для индукционного алгоритма отсчёта дней до отъезда.

    На острове всего два цвета глаз и все об этом знают генетически. По ММИ каждый думает "если у меня глаза не из группы А, то группа А уедет через N дней, иначе у меня глаза из группы А и я вместе с ней уеду через N+1 дней". После отъезда группы А, группа Б понимает, что у неё оставшийся цвет глаз и также вся целиком уезжает. (Тут мы допускаем, что все уже успели увидеть цвет глаз всех остальных, иначе мы попадём в рекурсивную ловушку, которая замкнётся на том, было ли это сказано в условии)

    Отказаться от подсчёта нельзя для простоты, иначе встанет вопрос о том, можно ли узнать уехал кто или нет, что опять ведёт нас к обсуждению условия.


    Итого: вопрос в задаче не имеет смысла, так как никак не зависит от туриста — это всё равно, что спросить, станет ли верным выражение 2+2=4, если 3 заменить на 5!


    Давайте ещё раз вернёмся к задаче — там спрашивается как поменяется жизнь на острове после отъезда туриста, но нигде не говорится (или я уже не могу найти), что островитяне собрались вместе ("во всеуслышание" этого не означает), как и о том, что они не собрались в момент отъезда туриста. Как поменяется погода на острове после отъезда туриста? :)

    ОтветитьУдалить
  12. Quark Fusion, похоже, что Вы не поняли, при каких условиях индукционное рассуждение корректно.

    Пусть у нас на острове ровно 2 человека: голубоглазый и кареглазый. Каждый из них видит ровно одного человека с противоположным цветом глаз, верно? Предложите, пожалуйста, рассуждение, позволяющее хотя бы одному из них вычислить свой цвет глаз (без высказывания туриста).

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

    ОтветитьУдалить
  13. Я утверждаю, что им достаточно собраться вместе при тех условиях, что были указаны, а именно — что островитян с одним цветом глаз как минимум 3. При этом вводные "на острове есть островитяне с таким цветом глаз", "все знают, что на острове есть островитяне с таким цветом глаз" выполняются, а уже приняв эти вводные начинается рассуждение "а что, если бы на острове остался один островитянин с таким цветом глаз, т.е. остался из тех, что были на острове".

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

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

    ОтветитьУдалить
  14. Дополнение ко второму абзацу: не только не будет нового цвета, но и существующий не исчезнет. Если принять возможность случайного исчезновения всех островитян с одним цветом глаз, кроме одного, то у этого одного не будет способа высчитать свой цвет глаз.

    ОтветитьУдалить
  15. Вообще на самом деле не имеет значения из верной цепочки рассуждения был получен способ отсчёта (я утверждаю, что из верной) или не верной (как вы утверждаете) — этот способ был найдет, а я помню, что в условии было упоминание о том, что до любой умной мысли островитяне догадаются, если до этого можно догадаться — что мешает им построить на первый взгляд ошибочную цепочку, но из неё извлечь работающий способ? После нахождения способа, который позволит им высчитать цвет глаз и знания о том, что все остальные также нашли этот способ нет никаких оснований им не воспользоваться, т.к. он фактически ведёт к угадыванию своего цвета, а островитяне опять-таки по условию обязаны до всего догадываться при наличии такой возможности.

    ОтветитьУдалить
  16. Quark Fusion, хорошо, давайте разберём Ваш случай.

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

    Я всё ещё не могу понять, как это возможно. Объясните мне, пожалуйста.

    ОтветитьУдалить
  17. В общем, прежде чем дальше спорить, давайте ещё раз проясним одну вещь: известно ли островитянину, что у него не могут быть глаза любого другого цвета или не известно?

    ОтветитьУдалить
  18. Quark Fusion, в чём вопрос? В первом же пункте условия задачи сказано: «На острове 888 кареглазых и 111 голубоглазых сектантов. Они легко могут видеть друг друга и знают, что людей с другим цветом глаз на острове не может быть.»

    ОтветитьУдалить
  19. Вот вам для случая, если известно (простите, не могу остановиться :) ):
    Реальный островитянин видит троих голубоглазых и думает: вот один из этих троих мог бы видеть два и стал бы думать, что… Доходим до последнего, он бы думал так "вот я не вижу голубоглазых, но от сведений общего разума я знаю, что на острове голубоглазых видят (первому ясно, что голубоглазые видят друг друга) — значит я голубоглазый и должен уезжать". Если первый не уезжает, значит он всё-таки не единственный голубоглазый по его собственному выводу, значит второй, который видит единственного голубоглазого понимает, что второй голубоглазый — это он. Если на второй день второй не уезжает, то уже третий понимает…
    Вот такое вот объяснение, оно отличается тем, что всем воображаемым островитянам известна решающая информация, которой безусловно обладают все реальные островитяне, а значит нет оснований предполагать, что воображаемый островитянин, который отражает ход мыслей реального островитянина вдруг ни с того, ни с сего потеряет это важное знание.

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

    ОтветитьУдалить
  21. Вот мне что не нравится: условие задачи дано с точки зрения стороннего наблюдателя, а решение должно рассматриваться с точки зрения островитянина, но островитянин не может видеть самого себя. Поэтому условие нужно поставить в виде того, что известно островитянину. Для случая всего с двумя островитянами это показывает, что я тут пытаюсь доказать.

    ОтветитьУдалить
  22. Я не понимаю это объяснение... Скорее всего, проблема в том, что в нём отсутствует середина. Приведите, пожалуйста, полный текст всего рассуждения. Тогда я или укажу на ошибку в нём, или пойму, где заблуждаюсь.

    ОтветитьУдалить
  23. Эх, уже второй час не могу из дома выйти :) …

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


    Вот еще раз прошлое объяснение без пропусков:
    Реальный островитянин видит троих голубоглазых и думает: вот один из этих троих мог бы видеть два и стал бы думать, что… один из тех видит одного голубоглазого и стал бы думать что…
    …он бы думал так "вот я не вижу голубоглазых, но из начальных вводных, полученных от реального островитянина, который меня воображает, я знаю, что на острове голубоглазых видят (первому ясно, что голубоглазые видят друг друга) — значит я голубоглазый и должен уезжать". Если первый не уезжает, значит он всё-таки не единственный голубоглазый по его собственному выводу, значит второй, который видит единственного голубоглазого понимает, что второй голубоглазый — это он. Если на второй день второй не уезжает, то уже третий понимает, что, кроме тех двоих есть ещё и он и уезжает вместе с ними.
    Ну а те трое кареглазых, которые остались, понимают что голубоглазые завершили эту цепочку ожидания (это как бы четвёртый островитянин, у которого не оправдалось ожидание, что голубоглазых 4) и им также приходится уехать, так как теперь известно, что остались одни кареглазые.

    ОтветитьУдалить
  24. Ещё раз: все воображаемые голубоглазые располагают информацией, что голубоглазые видят друг друга и единственный голубоглазый принимает это как "я вижу самого себя", а раз он себя видит — то знает свой цвет глаз и должен уехать.

    ОтветитьУдалить
  25. В общем задача находится в таком состоянии, что жизнь на острове изменится независимо от туриста, так же как меняется погода. Само доказательство, рассматривающее туриста как решающий фактор неверно. Это нашему подсознанию очевидно, но разум цепляется за проверку верности доказательства и располагая информацией от подсознания, что жизнь изменится, а доказательство неверно, но не понимая почему именно (сам процесс рассуждения верен), встаёт в ступор из-за двух взаимоисключающих вещей.

    Те, кому подсознание не подсказывает, что все свалят с острова просто заявляют, что ничего не изменится, а те, кому подсказывает — не понимают как с эти связан турист (что естественно) и впадают в ступор — задача-детектор. :)

    ОтветитьУдалить
  26. Quark Fusion:

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

    >Реальный островитянин видит троих голубоглазых и думает: вот один из этих троих мог бы видеть два и стал бы думать, что… Доходим до последнего, он бы думал так "вот я не вижу голубоглазых, но от сведений общего разума я знаю, что на острове голубоглазых видят (первому ясно, что голубоглазые видят друг друга) — значит я голубоглазый и должен уезжать".

    Ошибка во втором предложении: до приезда туриста не существовало общего знания о том, что на острове есть голубоглазый. Просто все знали это, но не знали, знают ли другие (при Г=2). Или знали, что другие тоже знают, но не знали, что другие знают, что все знают (наш случай, Г=3) и т. д. Представляя себе соседей, никто не имеет права "дарить" их образам свои личные знания.

    >А для случая с всего двумя островитянами, если сохраняется это ваше условие, что на острове есть и кареглазые и голубоглазые, то они тут же понимают, какой у кого цвет глаз!

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

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

    Во-первых, воображаемых островитян n-го уровня вложенности 2 в степени n, так как каждый акт воображения предполагает два варианта - с кареглазым и голубоглазым Я. В этом случае воображаемых Третьих 2*2=4, и они видят разное число голубоглазых. Один не видит ни одного Г, двое видят ровно одного Г и еще один - двух Г. Сразу после заявления туриста только один воображенец уедет с острова, а трое его близнецов останутся. А Вы говорите о них, как о единой личности (это, конечно, можно делать, но только пока у "единой" личности не возникнет разногласий с самой собой).

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

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

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

    ОтветитьУдалить
  27. Colog, вам не за что просить прощения :) Вы не виноваты :)

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

    >Но это мы знаем, что на острове есть и те и другие, а островитяне всего лишь знают, что нет третьих. То есть, пока у них нет доказательств обратного, они могут допускать как полностью кареглазый, так и полностью голубоглазый остров.
    Вот про это я спрашивал, когда упомянул известны ли островитянам все существующие цвета, а значит они не могут допускать существования меньшего количества цветов. Ещё раз вернусь к той проблеме, что условие стоит не с точки зрения островитянина, а стороннего наблюдателя, а надо рассматривать условие с точки зрения островитянина.

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

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


    Так, вот мы подошли к главному — теперь, внимание, вы пишите:
    "представляя себе соседей, никто не имеет права "дарить" их образам свои личные знания и тем более знание о том, что их воображает какой-то конкретный островитянин. Это уже будет не честный анализ потенциально возможных вариантов, просто фантазия."
    Любой из соседей видит не то, что видит любой из островитян — в его видение он сам заменён на другого островитянина с возможно отличным цветом глаз, но на этом всё! То есть для случая, когда у замены такой же цвет глаз он имеет право рассматривать его как самого себя, а в другом случае просто делает поправку на цвет глаз, пройдя рекурсию он приходит опять к эти двум вариантам.
    Образ мышления всех островитян одинаков по условию, а значит любой островитянин имеет право рассмотреть два случая N и N+1 голубоглазых. Вы же думаете, что островитяне думают по-разному в зависимости от количества голубоглазых, что не так.

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

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

    ОтветитьУдалить
  28. Возможно, мой ключевой вопрос был неправильно понят, правильно он должен был выглядеть так: известно ли островитянину, что у него не могут быть глаза любого другого цвета, кроме тех, что он наблюдает, или не известно?
    То есть фактически известно ли островитянину общее количество цветов, которые присутствуют на острове.

    ОтветитьУдалить
  29. И кстати, я хочу не столько узнать ответ на этот вопрос, сколько то, как вы понимаете этот ответ.

    ОтветитьУдалить
  30. Анонимный14.02.2010, 16:32

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

    ОтветитьУдалить
  31. Quark Fusion: по поводу ключевого вопроса. Есть общее знание, что природой предусмотрено ровно два цвета глаз - голубой и карий. Это знало бы даже отродясь не видевшее кареглазых голубоглазое население воображаемого острова. А вот о том, представлены ли на острове оба цвета глаз, до приезда туриста общего знания не было, а были только личные наблюдения - у каждого свои.

    Итак, сам ответ: тот, кто видит и кареглазых, и голубоглазых, точно знает число цветов на острове. Тот, кто видит только один цвет, знает, что на острове либо один, либо два цвета глаз.

    Следующим комментарием постараюсь ответить на остальные возражения.

    ОтветитьУдалить
  32. Ну вот "природой предусмотрено" это более широкое определение, чем "есть в наличии", что затрудняет объяснение. Однако в условии легко от него избавится — приняв все условия становится ясно, что есть все основания заменить "природой предусмотрено" на "есть в наличии", давайте докажем это и изменим условие — после этого станут понятны мои доводы.
    Очевидно же, что если на острове сотня голубоглазых и еще больше кареглазых и они друг с другом встречались и других цветов глаз нет, то все знают, что на острове не может быть единственный цвет глаз и тогда вариант всего с двумя островитянами решается сам собой.

    ОтветитьУдалить
  33. Анонимный, вы это кому? Все, кто активно обсуждает задачу привели свои варианты решения, даже в самой изначальной задаче решения уже были — вопрос какое решение и почему неправильно.

    ОтветитьУдалить
  34. Ответ же на задачу 1 в этом посте — лишить островитян информации о том, кто покинул остров, а на вторую — тот же, что и на исходную.

    ОтветитьУдалить
  35. Quark Fusion: вот то-то и оно, что есть принципиальное различие между "природой предусмотрено" и "есть в наличии" - задачи получаются совсем разные. Ведь турист как раз принес общее знание "есть в наличии" общим в дополнение к уже существующему "природой предусмотрено". Если бы знание "есть в наличии" было общим изначально... даже и не знаю, что было бы - либо островитяне уехали бы еще до туриста, либо остались бы и после его отъезда.

    ОтветитьУдалить
  36. Ну вот я и пытаюсь прояснить вопрос о том, было ли это знание — если все друг друга видели и известно, что других цветов нет, то оно однозначно было. Докажите мне, что хоть один из островитян знал о существовании реального островитянина, который не знал о существовании голубоглазых.

    ОтветитьУдалить
  37. Quark Fusion, островитянам известно, что бывает только два цвета глаз: голубой и карий. Но они не знают, все ли возможные цвета представлены на острове в данный момент. Теоретически, может так случиться, что на острове собрались только кареглазые или только голубоглазые.

    Другими словами, на Ваш вопрос «известно ли островитянину, что у него не могут быть глаза любого другого цвета, кроме тех, что он наблюдает, или не известно?» ответ однозначный: нет, ему это не известно.

    ОтветитьУдалить
  38. Quark Fusion:
    >Докажите мне, что хоть один из островитян знал о существовании реального островитянина, который не знал о существовании голубоглазых.

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

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

    1. На острове 1 Г. Он не знает, есть ли на острове Г, а после приезда туриста узнает.

    2. На острове 2 Г. Они знают, что на острове есть Г. Но они не знают, знают ли все, что есть Г.

    3. На острове 3 Г. Они знают, что есть Г и знают, что все знают, что есть Г. Но они не знают, знают ли все, что все знают, что на острове есть Г.

    И так далее. Чем больше голубоглазых, тем больше они знают, но все равно остается утверждение, которого они не узнали бы без туриста. В исходной задаче, где Г=111, в этом утверждении было бы 111 слов "знают", и можно даже не пытаться понять его смысл непосредственно, не прибегая к помощи диаграмм или индуктивного рассуждения.

    ОтветитьУдалить
  39. Моё мнение, что Шойгу надо изолировать или туриста, как предполагалось или островитянина, чтобы он не услышал туриста.

    ОтветитьУдалить
  40. Если же Шойгу доложили о туриста после того как он уже взболтнул лишнего, то нужно разобраться как следует, почему доложили так поздно (разведка что спит?) и наказать кого попало.
    Потом нужно Шойгу лично полететь на тот остров, собрать всех и сказать: "турист имел ввиду конкретно Васю (голубоглазого) и только это". После это Вася, конечно, уедет, на зато "цепная реакция" будет остановлена.

    ОтветитьУдалить
  41. Какая связь со второй задачкой лично мне не понятно. Из второй задачки ясно, что пять лет никто не куда ехать не будет, так как "ещё рано". Из-за того, что неизвестно как изменится популяция через 5 лет не возможно сделать вывод об истинности или ложности утверждения о голубоглазых сегодня. Поэтому в этом случае пять лет будут жить как жили, а потом всё как в первоначальной задаче.

    ОтветитьУдалить
  42. Анонимный14.02.2010, 23:36

    ---
    И так далее. Чем больше голубоглазых, тем больше они знают, но все равно остается утверждение, которого они не узнали бы без туриста. В исходной задаче, где Г=111, в этом утверждении было бы 111 слов "знают", и можно даже не пытаться понять его смысл непосредственно, не прибегая к помощи диаграмм или индуктивного рассуждения.
    ---

    Представьте ситуацию: вы - сектант с острова.
    Перед вами 50 голубоглазых и 100 кареглазых. Вы не знаете свой цвет глаз.

    Вы знаете, что на осрове есть голубоглазый? Да.
    Вы знаете, что на острове есть кареглазый? Да.
    Вы знаете, что каждый из 150 других сектантов видит и Г и К? Да.
    Вы знаете, что каждый из этих 150 сектантов:
    -видит Г (Да)
    -видит К (Да)
    -знает, что каждый из других 150 (включая вас) видит и Г, и К (Да)
    -знает, что каждый из 150 (включая вас) знает, что каждый из 150 (включая себя) знает что:
    --... ДА

    Заметили разницу между предыдущими рассуждениями и этим?
    Тут вы не убираете из расчетов себя, ибо вы есть. И вы знаете, что ваш цвет глаз повлияет лишь на +-1 в количество видимых Г или К другими.

    С каждым вложением мнимых островитят не происходит их общего уменьшения.


    Уже после двух вложений вы знаете, что каждый островитянин знает о наличии и Г и К, а так же знает, что об этом знает каждый другой островитянин.

    Так что турист не дал никакого общего знания. Оно было задолго до этого.

    Вы зна

    ОтветитьУдалить
  43. Возможно, я впадаю в маразм...
    Насколько я понял, главная проблема в том, что не все знают, что все знают, ... что на острове есть голубоглазый. Если я не прав, можете дальше не читать.
    Так вот, посмотрим глазами голубоглазого (для кареглазого чило Г на 1 больше). Он видит 110 Г, и ему также совершенно очевидно, что каждый из жителей видит (видел за жизнь, если это не собрание) как минимум 109 Г. Что мешает ему на этом остановиться, зачем всякие вложенные представления?
    Не вижу другой миссии туриста, кроме как в запуске таймера :(

    ОтветитьУдалить
  44. Анонимный15.02.2010, 01:57

    Имхо, народ впадает в ступор от большого числа итераций, который в голове не умещается. Надо оперировать числом 3 а не 110, все возражения по поводу 110 вполне применимы и к этим 3, зато решение куда понятнее.

    ОтветитьУдалить
  45. Анонимному:
    Зря взяли сразу 50 голубоглазых - ведь пока Вы добрались бы до того, чего они не знают, сообщение распухло бы до десятков экранов.

    -все видят Г и К - да
    -все знают, что все видят Г и К - да
    -все знают, что все знают, что все видят Г и К - да
    ...
    -все знают, что все знают (и так 50 раз), что все видят Г и К - НЕТ

    >Заметили разницу между предыдущими рассуждениями и этим?
    Тут вы не убираете из расчетов себя, ибо вы есть.

    Странно, я как раз всегда рассматривал точку зрения каждого островитянина и даже то, как он лично будет рассматривать чужие точки зрения. Дело в другом: +-1 плюс +-1 будет +-2, и 50 плюс-минусов достаточно, чтобы превратить 50 в возможный ноль.

    Пусть на острове 50 Г и 100 К, я - Г, но этого не знаю.

    1. Я знаю, что на острове не менее 49 Г.
    2. Я знаю, что все знают, что на острове не менее 48 Г.
    3. Я знают, что все знают, что все знают, что на острове не менее 47 Г.
    ...
    50. Я знаю, что все знают, ... , что на острове не менее 0 Г

    №50 знал бы даже слепой: число людей просто физически не может быть отрицательным. А вот после сообщения туриста в утверждении 50 вместо нуля будет единица - какое-никакое знание.

    ОтветитьУдалить
  46. Алексей:
    Вы правильно поняли, турист действительно дает новую информацию на уровне глубоко вложенных представлений. Что мешает жителям остановиться и не рассматривать их? То, что они по условию обязаны догадываются до всего, до чего можно догадаться, а значит, и до вложенных представлений. Приведу еще аналогию с шахматами: зачем просчитывать ходы соперника на десять вперед, если можно прямо сейчас съесть ферзя?

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

    ОтветитьУдалить
  47. Анонимный15.02.2010, 15:57

    ---
    -все знают, что все знают (и так 50 раз), что все видят Г и К - НЕТ
    ---
    Почему нет? Я показал не мнимых, а реальных сектантов!
    Именно каждый сектант знает, что на острове есть 50+-1 Г и 100-+1К, а так же каждый знает что каждый об этом знает. А так же каждый знает, что каждый знает что каждый знает.
    Всё, за эти три иттерации каждый РЕАЛЬНЫЙ сектант знает что все знают. Все остальные иттерации просто не нужны, так как возникает рекурсия. Тут нет цикла с Г>>0.

    Потому предположение о том, что кто-то не знает о том, что на острове 50+-1 Г и 100-+1К - ложно.
    А так как оно ложно, то никто не имеет право допускать такое утверждение в просчете мнимых копий.

    Отстраняясь от точных подсчетов количества построим цепочку знаний каждого реального островитянина:
    1. Каждый знает, что на острове есть толпа Г и толпа К.
    2. Каждый знает, что каждый может видеть толпу как Г, так и К.
    3. А значит каждый знает, что каждому известно о том, что каждый видит толпу как Г, так и К.
    Что еще требуется знать каждому?

    Нет никаких оснований предполагать, что кто-то не знает о существовании Г на острове. Это очевидный факт.

    P.S.
    Я знаю, что вы уверены в своем варианте решения и считает его правильным.
    Я так же догадываюсь, что вы считаете что я не могу осознать ваше решение, потому иду по пути меньшего сопротивляния, который по вашему варианту ложен.
    Это не так, я понимаю ход вашего решения. Вот только я против главного утверждения, на ниточке которого держится вся ваша теория (что кто-то может предположить, что кто-то не видит Г).

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

    ОтветитьУдалить
  48. Анониму:
    >Именно каждый сектант знает, что на острове есть 50+-1 Г и 100-+1К, а так же каждый знает что каждый об этом знает. А так же каждый знает, что каждый знает что каждый знает.

    Интересно, откуда у них взялась такая информация. Не из собственных наблюдений точно. Может быть, от туриста?

    >1. Каждый знает, что на острове есть толпа Г и толпа К.
    >2. Каждый знает, что каждый может видеть толпу как Г, так и К.
    >3. А значит каждый знает, что каждому известно о том, что каждый видит толпу как Г, так и К.
    >Что еще требуется знать каждому?

    Слышали про парадокс кучи? Если из кучи песка вытащить песчинку, то куча останется кучей. Следовательно, какое угодно число песчинок, взятое из кучи песка, оставит кучу кучей. Значит, либо в куче песка бесконечно много песчинок, либо даже пустое место - это куча песка. Поэтому вместо нечеткого понятия толпы лучше пользоваться точными числами.

    >Нет никаких оснований предполагать, что кто-то не знает о существовании Г на острове. Это очевидный факт.

    Согласен, если Г>1.

    >я понимаю ход вашего решения. Вот только я против главного утверждения, на ниточке которого держится вся ваша теория (что кто-то может предположить, что кто-то не видит Г).

    Похоже, Вы понимаете его не до конца - мое решение держится не более сложном утверждении. Да, при Г>2 никто не может предположить, что кто-то не видит Г. Зато при Г=3 кто-то может предположить, что кто-то может предположить, что кто-то не видит Г.

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

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

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

    ОтветитьУдалить
  49. Дмитрий15.02.2010, 20:23

    Хотелось бы уточнить условия:

    1. Шойгу узнал уже о прощальной фразе туриста или он еще может его опередить?

    2. Надпись в пещере видела ограниченная группа ученых или все островитяне?

    ОтветитьУдалить
  50. Спасибо, colog, теперь все вроде встает на места :)

    ОтветитьУдалить
  51. colog, спасибо, что даёте такие чёткие и краткие ответы! Я думаю, многие поняли изюминку этой задачки именно благодаря Вам.

    Дмитрий, да, это я не очень чётко сформулировал... Министр узнал о ЧП по факту - когда турист уже уплыл.

    Надпись в пещере прочитали все островитяне.

    ОтветитьУдалить
  52. Илья Весенний, а я-то боялся, что своими простынями заумного текста только мешаю не понявшим задачу додумать самостоятельно, а понявшим - обсудить более интересные моменты (например, указанные в этом самом посте). Прошу прощения и обещаю впредь не дискутировать с Вашими посетителями.

    ОтветитьУдалить
  53. colog, такое ощущение, что мои слова благодарности Вам были выражены не очень ясно. Вам не за что просить прощения и не надо игнорировать вопросы других читателей!

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

    ОтветитьУдалить
  54. Анонимный16.02.2010, 13:55

    1-я задача. Шойгу нужно увезти с острова любого голубоглазого. Тогда на 100м уровне рассуждений все смогут предполагать, что на острове нет голубоглазых, и смогут не уехать.
    2-я задача. Вот это действительно зубодробительная задачка, и пока ничего не могу сказать :)
    Хочу только уточнить - каждый турист на 100% уверен в истинности пророчества?

    ОтветитьУдалить
  55. va1ergrad, по поводу Вашего второго вопроса: какой каждый турист?

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

    ОтветитьУдалить
  56. Анонимный16.02.2010, 15:55

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

    Но думаю, вопрос был не в том, будет ли слова туриста правдивы.
    Вопрос в том, все ли уверены, что турист точно приедет ровно через 5 лет и точно скажет фразу?
    И все ли уверены, что все уверены что все... Игра слов, в общем =)

    ОтветитьУдалить
  57. Прочитал все посты и не могу не высказаться. Мое утверждение будет основано на:
    1) Все островитяне знают, что на острове есть кареглазые и есть голубоглазые;
    2) Все островитяне очень умные, то есть могут логически догадаться до чего угодно.
    Как уже говорил Илья Весенний островитяне никогда не станут лениться в определении своего цвета глаз. Также хочу отметить, что в условии не сказано, что они немые социопаты. Соответственно, как только встречается три островитянина, у одного из которых цвет глаз отличен от цвета глаз другого, то сразу же произойдет следующее. Для определенности - 1Г, 2К. Один К спрашивает у другого К одного ли цвета глаза у него и у Г, тот отвечает - нет. Потом этот вопрос задается Г, тот отвечает да. В данном случае остается вопрос - знают ли они как выглядит голубоглазый и как выглядит кареглазый. Тут вступает в игру Турист.
    Считаю обснованным вывод, что после заявления Туриста (при условии, что его слышали все островитяне) все уедут с острова. Шойгу никому уже ничем не поможет.

    ОтветитьУдалить
  58. Дмитрий16.02.2010, 21:06

    Еще вопрос по условию. Возможно ли попасть на остров незамеченным местными жителями?

    ОтветитьУдалить
  59. Дмитрий, все жители знают друг друга в лицо, поэтому нового человека сразу обнаружат. Я только не уверен, что правильно понял Ваш вопрос. Уточните, пожалуйста, если этот мой ответ не прояснил ситуацию.

    ОтветитьУдалить
  60. Дмитрий17.02.2010, 20:58

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

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

    ОтветитьУдалить
  61. Дмитрий, да, министр может тихонечко прокрасться на остров, если ему это надо. Сотрудники МЧС имеют необходимую технику и подготовку :)

    ОтветитьУдалить
  62. Дмитрий17.02.2010, 21:21

    В таком случае, я думаю, что можно их всех спасти. Причем министру надо не столько самому ехать, сколько послать подходящего агента.

    ОтветитьУдалить
  63. Дмитрий, я думаю, уже давно пора озвучивать решения, потому что прошло достаточно много времени.

    ОтветитьУдалить
  64. Дмитрий18.02.2010, 19:37

    ОК, я просто сомневался в корректности такого действия - может, кто-то еще думает (ну прямо как на том острове - я думал, что кто-то думает...:)).

    Итак, агент МЧС тайно проникает на остров. Затем предстает перед островитянами и говорит:

    - А я давно тут уже брожу по вашему острову. Вот, на днях встретил американского туриста, который принял меня за местного.

    Рассказывает, а сам так и сверкает своими голубыми глазами.

    - А теперь мне пора уезжать. А вам счастливо оставаться!

    ОтветитьУдалить
  65. Дмитрий18.02.2010, 20:38

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

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

    ОтветитьУдалить
  66. Дмитрий18.02.2010, 20:59

    А еще у меня есть такая мысль, что можно обойтись и без помощи извне. Островитяне ведь сразу поняли, что произошло, они же умные. Конечно, они еще не могут вычислить цвет своих глаз, но осознают, что это вопрос времени. Турист уплыл, до следующего парома сутки, надо действовать. Остров делится на две части, возводится высокий забор. Народ делится на две примерно равные группы (с точностью до единицы, с учетом нечетности) случайным образом. Дальше эти группы живут изолированно. Неприятно, но во имя спасения. Если оказывается так, что в каждой группе есть голубые глаза, то каждая группа знает про другую, что там они есть, а про свою не знает. Если же волей случая одна группа полностью кареглазая, то у нее проблем нет, а вот другая группа знает, что среди них есть голубые глаза. Тогда она, уже изолированная от первой группы, делит свою половину еще пополам. При имеющемся раскладе, возможна еще пара делений. Увы, нарушена дружная целостность острова.

    ОтветитьУдалить
  67. Дмитрий18.02.2010, 22:16

    Уточнение. Говоря, что группа не знает о наличии в ней голубых глаз, я имел в виду общее знание, каждый-то может и знать.

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

    ОтветитьУдалить
  68. Илья Весенний комментирует...

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

    Другими словами, на Ваш вопрос «известно ли островитянину, что у него не могут быть глаза любого другого цвета, кроме тех, что он наблюдает, или не известно?» ответ однозначный: нет, ему это не известно.


    Ну вот я не понимаю! Как может быть, что "Но они не знают, все ли возможные цвета представлены на острове в данный момент." + максимальное количество цветов — два + минимально одного цвета — 110. При таком большом минимуме и вводной о максимуме цветов должно быть очевидно, что этих цветов не менее двух для всех островитян. Если это не так, то островитяне допускают существование зелёноглазых, а вы говорили, что это не так!

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

    ОтветитьУдалить
  69. дополнение: не одного цвета 110, а с разными цветами — 110

    ОтветитьУдалить
  70. Хех, про вероятность вот вам задача: какова вероятность, что Билл Гейтс, узнав про остров, ради шутки спустил на него огромное зеркало, затмив солнце и так удивив всех островитян, что они подняли свой взор и увидели в отражении цвет своих глаз?

    P.S. всех читающих с праздником!

    ОтветитьУдалить
  71. Quark Fusion, складывается впечатление, что Вы не читаете ответы на свои вопросы, потому что повторяете их снова и снова. Вас тоже с праздником! :)

    ОтветитьУдалить
  72. Дмитрий23.02.2010, 14:53

    Всех с праздником!

    Quark Fusion, Если в Вашем вопросе «известно ли островитянину, что у него не могут быть глаза любого другого цвета, кроме тех, что он наблюдает, или не известно?» ключевое слово "любого", то кое-что ему об этом все же известно. Именно то, что они не могут быть зелеными, серыми и вообще какими-либо, кроме карих и голубых. Для них просто в природе других не бывает.

    "Ладно, можно допустить, что 108 голубоглазых случайно узнали цвет своих глаз..." -
    нет, случайно они их не узнают.

    Похоже, Вы пытаетесь доказать, что знание каждого автоматически образует общее знание. А это не так. Сколько бы островитян ни было, с каким бы то ни было распределением цветов глаз, "общее знание" существенно отличается от "знания каждого". Пожалуй, лучше и нагляднее, чем colog, это уже сложно объяснить. Вернитесь к его рисункам и комментариям.

    И давайте посмотрим на мир с точки зрения голубоглазого островитянина. Контрольный вопрос: сколько голубоглазых на острове? До приезда туриста - 110 или 111, точнее он ответить не может, т.к. это зависит от цвета его собственных глаз, а он его не знает.

    После отъезда туриста становится истинным следующее утверждение: если за N дней никто не уехал, то голубоглазых на острове не менее N+1. Значит, в течение 110 дней его ответ не изменится, а через 110 дней он уже определенно будет знать, что на острове голубоглазых не менее 111. Но он и раньше знал из собственных наблюдений, что их не больше 111. Следовательно, их ровно 111, и 111-й - это именно он. И так рассуждает каждый голубоглазый. Каждый кареглазый рассуждает в принципе так же, только с другими числами: 111/112.

    Информация туриста заключается в том, что до его приезда из того, что никто не уезжает, ровным счетом ничего не следовало, а после его отъезда из этого уже можно делать выводы.

    P.S. А Билл Гейтс не так уж и страшен. Даже если он и спустит на остров зеркало, то какова вероятность, что это был не Photoshop? :)

    ОтветитьУдалить
  73. Дмитрий, вы всё очень хорошо объяснили. Думаю, про общее знание нужно поговорить отдельно, чтобы оно не образовывалось островитяне должны достаточно по-разному мыслить, чтобы не могли делать выводы о мыслях других. Однако, в этом случае получается противоречие, об этом далее.

    Да, каждый островитянин знает, что голубоглазых 110 или 111 — это я и пытался донести. Отсюда следует, что он знает о наличии других голубоглазых на острове, что тут многие упорно отрицали.

    Утверждение после отъезда туриста становится истинным только в том случае, если все островитяне сделали общий вывод о том, что все другие островитяне сделали тот же вывод о том, что все островитяне получили точку отсчёта и начали считать.
    Моё упорство заключается в том, что могло возникнуть любое другое событие, которое запустило бы этот процесс. Также вывод "ага, он сказал "голубоглазый", значит все должны переключить свой разум на мысль о подсчёте голубоглазых" не абсолютен — слово "голубоглазый", а конкретно то, что на острове есть голубоглазый, не привносит новых сведений островитянам, а следовательно, не может служить "переключателям" для 100% островитян и не приводит к общему знанию.
    Вы считаете, что островитяне делают догадки об общем процессе мышления также, как и вы, и не делают их в тех же случаях, что и вы. Моё мышление отличается от вашего, следовательно я делаю вывод, что найдётся хотя бы один островитянин, который подумает также и не поддастся стадному мышлению, однако это противоречит условию, что все островитяне одинаковы. Если допустить одинаковость мышления всех островитян мы придём к выводу, что упоминание голубоглазых либо послужит "переключателем", либо не послужит — в зависимости от устройтсва разума островитян. (Здесь нужно куда-то вставить мысль о том, что если все островитяне одинаково мыслят, то они придут к общему знанию.) Однако, условие говорит нам о том, что островитяне максимально умные, а следовательно из этих двух вариантов нужно выбрать более умный. В первом варианте нет никаких математических причин, следующих из условия, чтобы сделать вывод о наличии связи "упоминание голубоглазых —> запуск процесса подсчёта островитян", поскольку турист не принёс на остров новых сведений. Если допустить эту связь, то нужно допустить возможность существования другой связи, ведущей к этому же процессу, а значит нельзя говорить о стабильности системы до приезда туриста, возможно она уже "катится вниз".

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

    ОтветитьУдалить
  74. Дмитрий07.03.2010, 23:42

    Quark Fusion,
    Да, каждый островитянин знает, что голубоглазых 110 или 111 — это я и пытался донести. Отсюда следует, что он знает о наличии других голубоглазых на острове, что тут многие упорно отрицали.

    Как раз именно этого никто не отрицал. Для голубоглазого - 110 или 111, для кареглазого - 111 или 112. В дальнейших рассуждениях будем смотреть на мир голубыми глазами, все равно они по сути одинаково мыслят. Вот именно, что через 110 дней после отъезда туриста пропадает это "или". Ровно 111. Уже из этого следует наличие информации. Они же и до туриста могли сколько угодно думать. Не могли только прийти к выводу.

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

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

    ...упоминание голубоглазых либо послужит "переключателем", либо не послужит...

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

    если все островитяне одинаково мыслят, то они придут к общему знанию

    К общему знанию они не "приходят". Сам факт публичного заявления создает общее знание. А "приходят" они к выводам на основе этого знания. И не имеют права не прийти. По условию. Вот уж воистину, горе от ума.

    "упоминание голубоглазых —> запуск процесса подсчёта островитян"

    А это вовсе и не запуск процесса. Это именно информация, благодаря которой "110 или 111" в результате превращается в "ровно 111".

    воображаемый островитянин теряет часть сведений реального островитянина

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

    ОтветитьУдалить
  75. По-вашему получается, что реальный островитянин не знает какой он, как этого не знает и последний (а то бы сразу уехал), но последний предполагает цвет своих глаз, и если ему дать подтверждение (которое даёт турист), то цепочка разворачивается, воображаемые определяют кто из вышестоящих был неправ, понимают цвет своих глаз и, в итоге, реальный островитянин узнаёт цвет своих глаз — я правильно понимаю?
    С этой точки зрения рассуждение, в принципе, верно. Но только в принципе. В этом объяснении турист дал новую информацию, которая еще не была известна, а именно, о наличии голубоглазых на острове. Но на самом деле это не так — островитяне и так это знали, следовательно в рассуждении есть ошибка. Ошибка заключается в том, что знание о наличии голубоглазых было вычеркнуто, что я и пытаюсь доказать.

    ОтветитьУдалить
  76. Дмитрий08.03.2010, 22:03

    Quark Fusion,
    островитяне и так это знали

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

    Ошибка заключается в том, что знание о наличии голубоглазых было вычеркнуто

    Под вычеркиванием знания Вы понимаете тот факт, что на самом верхнем уровне вложенности существует версия полностью кареглазого острова? Но почему Вы считаете это ошибкой? Мы, сторонние наблюдатели, знаем, что их 111. Каждый из них знает, что их не меньше 110. Первый знает, что второй видит не менее 109. Он знает, что второй его видит, но не знает, каким он его видит. Также первый знает, что второй может быть уверен лишь в том, что третий видит не меньше 108, т.к. первый сам себя не видит, знает о том, что второй тоже себя не видит, и не знает о том, каким его, первого, видит второй. В конечном итоге, 1-й знает, что 2-й знает,..., что 111-й знает, что их не меньше нуля. А тут приходит турист и заявляет, что их не меньше единицы. Чем не информация? Из "не меньше нуля" ничего не следует, меньше некуда. А из "не меньше единицы" уже цепочка раскручивается.

    Если не убедил, то уточните, что именно Вы хотите доказать. Раз Вы утверждаете, что турист не дал информации, то одно из двух: либо они и без туриста имели достаточно информации, либо и после туриста им информации не хватает. Какой из этих вариантов?

    ОтветитьУдалить
  77. "они и без туриста имели достаточно информации" — единственное чего у них не было так это соглашения о начале точки остчёта, но этого соглашения не стало и после туриста.

    "111-й знает, что их не меньше нуля. А тут приходит турист и заявляет, что их не меньше единицы. Чем не информация?"
    Да, это-то как раз понятно, непонятно другое — каждый из 111 голубоглазых островитян видел 110 других, а значит достоверно знал, что голубоглазых как минимум 110. Воображаемый островитянин уже не знает что минимум 110 — здесь и произошла потеря знания.

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

    Цепочка размышлений о гипотетической ситуации позволяет найти алгоритм по подсчёту островитян, но для его запуска все островитяне должны быть уверены в том, что они его запустили синхронно! Поэтому и без туриста информации достаточно, но система находится в нестабильном состоянии, для её запуска нужно сказать что-то вроде "это был исторический момент и с него вы будете считать время". Именно соглашение о начале отсчёта времени может служить причиной для отъезда, а не известие о том, что на острове есть голубоглазые. (тут допускается, что островитяне уже нашли этот способ)

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

    Здесь не требуется общего знания, а требуется общее соглашение об алгоритме действия и следование ему. Именно алгоритм даёт общее знание, а не наоборот. (Каждый посмотрел на каждого — алгоритм, каждый понял, что каждый видел каждого — общее знание, полученное в результате действия всех по алгоритму, алгоритм гарантирует, что знание общее, если хотя бы один не следовал алгоритму, то знание уже не гарантировано). Поэтому для общего знания в том смысле, что "каждый знает, что все это знают", каждый должен быть уверен, что все следовали такому алгоритму, но тут получается рекурсия — для того, чтобы знать "что все следовали такому алгоритму" необходимо общее знание об этом. Таким образом само начало "общего знания" не может возниктуть самопроизвольно — оно должно быть задано для каждого индивидуума.

    Я хочу доказать, что всё, что могут сделать островитяне это догадаться до способа подсчёта цветов глаз, но не могут его применить, т.к. нет соглашения о точке отсчёта и никто из островитян не станет инициатором такого соглашения, потому как соглашаться узнать цвет своих глаз они не обязаны.


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

    ОтветитьУдалить
  78. Дмитрий09.03.2010, 19:35

    Quark Fusion,
    "они и без туриста имели достаточно информации" — единственное чего у них не было так это соглашения о начале точки остчёта

    Так за чем же дело стало? Давайте рассмотрим такой сценарий: вместо туриста приехал дирижер и сказал: "Сейчас я взмахну своей палочкой, и вот этот момент объявляется точкой отсчета". Предложите ход рассуждений конкретного голубоглазого, приводящий его к выводу о цвете своих глаз.

    Воображаемый островитянин уже не знает что минимум 110 — здесь и произошла потеря знания.
    ...но тут мы забывваем, что тот голубоглазый островитянин видит этого островитянина.


    Вовсе не забываем. Островитянин знает и помнит о том, что другие его видят, но не знает, каким они его видят. Воображаемый "я" первого уровня видит как раз тех же самых 110 других голубоглазых. На других уровнях они воображаются уже не собой реальным, а воображаемыми другими. То, что Вы называете "потерянным знанием" - вовсе не потерянное, его и не было. Каждый реальный голубоглазый видит других 110, но при этом вовсе не знает о том, что другие видят также 110, поскольку не знает, каким они видят его.

    цепочка рассуждений уменьшает количество одних островитян и увеличивает других

    Не уменьшает/увеличивает одних/других, а повышает неопределенность.

    любое событие, время которого было достоверно известно всем островитянам с точностью в одну единицу отсчёта

    Ну вот я предложил сценарий: началом отсчета послужит взмах дирижерской палочки, а единица хода времени - паром раз в сутки.

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

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

    ОтветитьУдалить
  79. Quark Fusion выше Вы писали следующее: «В объяснение colog ошибка заключается в том, что воображаемый островитянин теряет часть сведений реального островитянина.»

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

    ОтветитьУдалить
  80. Более точно будет сказать, что тереят вероятность — я эту тему еще не до конца развил, но мысль в том, что количество голубоглазых сильно меньше видимых возможно с вероятностью около нуля.
    В умопинаемой заметке вчера немного отписался на эту тему.

    ОтветитьУдалить
  81. Это не вероятностная задача, поэтому мне трудно понять, каким образом тут можно применять вероятностные соображения.

    ОтветитьУдалить

Понравилась заметка? Подпишитесь на RSS-feed или email-рассылку.

Хотите поделиться ссылкой с другими? Добавьте в закладки:



Есть вопросы или предложения? Пишите письма на адрес mytribune АТ yandex.ru.

С уважением,
      Илья Весенний