…в общем, это — прекрасное решение прекрасной задачи.
Жаль, что оно неверное.
Но как?!
Постойте, я же только что расписал это решение во всех деталях, да и на других сайтах описывается оно же. Что тут не так?
Да,
относительно этого сложного процесса нас тоже немного гложут сомнения,
но тут ведь как с квантовой механикой: «заткнись и считай». Рекурсия
сложна для понимания, но работает!
Вы знаете, особое изящество
этой задачи мне видится в том, что рекурсия тут действительно работает.
Причём на первых итерациях она даже интуитивно понятна, а на более
поздних рождает щекочущее нервы чувство чудесной научной мистики,
поэтому прямо-таки хочется поверить, что тут всё верно, ты только что
понял что-то очень нетривиальное, а те, кто продолжает с ним спорить,
просто «не догоняют» всей этой логической крутизны.
Однако
нетривиальность в первую очередь в том, что тут ошибки рассуждений
кроются в очень глубоких глубинах. Настолько глубоких, что во всех
дискуссиях об этой задаче, которые я встретил, люди, сомневающиеся в
правильности решения, находили «ошибки» не там, где они на самом деле
есть.
Иными словами, изящество этого «парадокса» в том, как
здорово в нём замаскированы несколько очень суровых натяжек — внутри
весьма изощрённого и «технологичного» решения.
В общем, вся эта
рекурсия работает, только если закрыть глаза на ряд вещей, которые в
условиях есть, и сделать ряд предположений, которых нет в условиях.
Спасительное противоречие
Дело
в том, что в решении задачи игнорируется одно из её условий: у туземцев
есть запрет на то, чтобы сообщать другим о цвете их глаз. Причём из
контекста понятно, что имеется в виду не только «говорить», но и
сообщать иным способом — рисовать на картинке, неожиданно показывать
зеркальце или давать некий ребус, решение которого идеально логичным
(это тоже есть в условии) туземцем привело бы к вычислению им
собственного цвета глаз.Так вот, в описанной ситуации туземцы совершенно точно дают друг другу такой ребус — ведь на этом построено всё решение со всей его рекурсией: их действия или бездействия приводят к тому, что в конечном счёте вообще все узнаю́т, какого цвета у них глаза.
Даже при наличии единственного голубоглазого его самоубийство оказалось бы «ребусом», сообщающим всем остальным, что они — кареглазые.
Иными словами, в традициях туземцев есть противоречие и правильный логический ответ, который каждый из них должен был бы сделать в этой ситуации, как идеальный логик: следует отменить эти противоречивые правила ещё до появления путешественника.
Если же эти правила не отменены, то в описанном случае им невозможно следовать, ведь хотя бы одно из них будет нарушено.
Вариант с неопределённостью
Условия
задачи не сообщают нам, какие именно приоритеты у туземцев. Вполне
возможно, что каждый из них счёл бы, что лучше нарушить одно правило,
чем два: не самоубиться, узнав цвет своих глаз, но зато и не сообщить
другим о цвете их глаз. Ведь альтернатива тому — нарушить правило о
знании цвета своих глаз, выполнить правило о самоубийстве, и тем самым
нарушить правило о несообщении.Если же приоритеты были никак не оговорены, то ни один туземец не может наверняка знать, какой вариант выберет другой туземец, а потому не может однозначно вычислить цвет своих глаз.
Даже единственный голубоглазый на острове мог бы счесть, что важнее не сообщать другим цвет их глаз, чем самоубиться после вычисления своей голубоглазости.
Однако, быть может, у туземцев всё-таки есть какие-то уточнения по этому поводу? Например, приоритет правил друг перед другом.
А, кстати, насколько они честны?
Если
туземцы могут говорить друг другу неправду, и все знают об этом, то
появляется выход из положения: сказать кому-то «ты — голубоглазый, но я,
быть может, наврал». Если все сделали бы так, самоубийство зависело бы
от того, поверил ли тот, кому это сказали, в сказанное или не поверил.
Таким образом, самоубийства не давали бы однозначной информации о
ситуации.
Единственного туземца это бы всё равно не спасло — он
бы точно вычислил цвет своих глаз методом исключения, но вот в случае с
двоими, ни один из них уже не мог бы знать наверняка, самоубился ли
другой на первый день потому, что он не видит других голубоглазых или же
потому, что поверил в сказанное ему «твои глаза — голубые».
Однако
есть правило, что туземцы совершают самоубийство только тогда, когда
точно знают цвет своих глаз, а не просто «верят» в него.
Одновременно с тем есть правило не сообщать никому цвет его глаз.
Если
возможен обман, то это правило теряет смысл — ведь сообщение цвета ни к
чему не приведёт. Даже изображение в зеркале можно подделать, не говоря
уже про устные сообщения.
Это подводит к мысли, что туземцы могут сообщать только правду, и все поголовно знают, что все остальные сообщают только правду.
Варианты с честными островитянами
Итак, из условий задачи косвенно следует, что островитяне не только идеально логичны, но ещё и абсолютно честны.
Именно
для этого случая мы и будем рассматривать варианты с приоритетами
правил. Тут в каждом пункте они перечислены в порядке убывания их
приоритета.
- Не сообщать другим цвет их глаз; самоубиться, если узнал свой; не знать цвет своих глаз.
- Не сообщать; не знать; самоубиться.
- Не знать; не сообщать; самоубиться.
- Самоубиться; не сообщать; не знать.
- Не знать; самоубиться; не сообщать.
- Самоубиться; не знать; не сообщать.
Не сообщать другим цвет глаз важнее,
чем самоубиться, если узнал
Варианты 1, 2, 3.
В
этом случае даже при наличии одного туземца процесс не пойдёт дальше —
он не будет самоубиваться, чтобы не нарушить более важное правило о
несообщении другим цвета их глаз, из-за чего не будет работать и
вышеописанная рекурсия.
Все выживут.
Не знать свой цвет глаз важнее,
чем не сообщать его другим
Варианты 4, 5, 6.
Поскольку
самубийство следует только после узнавания цвета своих глаз, в данном
случае без разницы, в каком порядке эти два правила расставлены по
приоритетам друг относительно друга. Следовательно, мы можем
рассматривать всё это как единый случай.
В этом случае у
единственного голубоглазого большие проблемы: он не может не узнать свой
цвет глаз, а самоубиться важнее, чем не сообщать.
Однако, если
голубоглазых больше одного, то ситуация уже меняется. Ведь если не знать
цвет своих глаз важнее, то следует сказать кому-то о цвете его глаз,
если это позволит не узнать цвет своих.
Кареглазым об этом
сообщать бесполезно — это не изменит положения вещей: ведь все
голубоглазые знают всех кареглазых и, таким образом, сразу же поймут,
что самоубийство кареглазого совершенно точно обусловлено тем, что им
кто-то напрямую сказал о цвете их глаз.
Следовательно, надо об этом сказать голубоглазому.
Даже
если такой всего один, то всё равно уже никто не может быть уверен,
покончил ли он с собой из-за того, что ему сообщили о цвете глаз, или же
потому, что он его вычислил (а, значит, рекурсивный метод — в деле, и
все остальные тоже автоматически вычислят свой цвет глаз).
Причём,
каждый конкретный островитянин, в принципе, может даже не сообщать об
этом самостоятельно — достаточно уже возможности того, что голубоглазому
о цвете его глаз сообщил кто-то другой: в этом уже есть достаточная для
невозможности вычисления своего цвета глаз всеми остальными
неопределённость.
Однако тут есть тонкость: если единственный
хотя бы один голубоглазый не самоубился, то, значит, ему не сообщили о
цвете его глаз. А раз так, то рекурсивное вычисление всё ещё возможно.
Поэтому
в данной ситуации с неизбежностью должен покончить с собой хотя бы один
голубоглазый, чтобы рекурсивный процесс застопорился.
Что
касается кареглазых, то для них ситуация идеальна — сколько бы ни было
голубоглазых, кареглазым точно не сообщат о том, что они — кареглазые,
поскольку это никак не поможет избежать вычисления цвета своих глаз, но
при этом у них не будет уверенности, потому ли им не сообщили, что они —
кареглазые, или потому, что они голубоглазые, которым повезло.
Иными
словами, в данном случае, в зависимости от везения, самоубьётся минимум
один голубоглазый, но вот все кареглазые и те голубоглазые, которым
повезло, выживут.
При наличии человеколюбия у туземцев, вообще
говоря, они должны догадаться, что тот, кто видит нескольких
голубоглазых, должен при всех сказать одному из них: «ты —
голубоглазый», а остальные должны промолчать — это сведёт количество
жертв к возможному минимуму — одной.
Важность определённости приоритетов
Как можно видеть по вышеприведённым рассуждениям, от ответа на вопрос о приоритетах зависит исход ситуации.
Если
приоритеты не определены, то, в зависимости от личных предпочтений,
возможно, что не самоубьётся даже единственный на острове голубоглазый.
Или же единственный голубоглазый самоубьётся, но остальные не будут
знать, это потому, что он — единственный, или потому, что кто-то счёл
более правильным вариантом неизбежного нарушения традиций сообщить
единственному голубоглазому, что он — голубоглазый. Если же голубоглазых
больше одного, то никто ни в чём не уверен, а потому выживут все.
Если не сообщать другим цвет их глаз важнее, чем самоубиться, если его ты узнал, то выживут все.
Если
не знать свой цвет глаз важнее, чем не сообщать его другим, то, в
зависимости от везения, самоубьётся от одного до полного количества
голубоглазых, но все кареглазые выживут.
Задача имеет разные
решения, в зависимости от тех условий, о деталях которых умолчали: как
правила по своей важности соотносятся друг с другом.
А что если запрета на раскрытие цвета глаз другого
нет?
Предположим,
что его действительно нет, просто из человеколюбия островитяне не
сообщали о цвете глаз других, пока не появился злосчастный
путешественник.
Однако, когда он появился, ситуация ведь
поменялась: теперь запущен процесс, который приведёт к нарушению запрета
на знание собственного цвета глаз. И если раньше — из человеколюбия — о
цвете глаз кому-то другому можно было не сообщать, то теперь и
человеколюбие, и традиции требуют сообщить об этом хотя бы одному
голубоглазому.
Минимум один туземец умрёт, но, возможно, этим дело и кончится. Кареглазые же однозначно выживут.
Изворачиваемся с условиями
В
общем-то, понятно, что хотели сказать авторы задачи. Что-то типа:
«островитяне не могут сообщать другим цвет их глаз, кроме как вот этими
вот своими самоубийствами».
Эта формулировка выглядит крайне
натянутой, однако рекурсивное решение приводит к вымиранию всего острова
только с ней — такой вот натянутой.
Или не приводит?
Lex Kravetski
🌴 🌴 🌴
Парадокс
голубоглазых островитян: