О, боже мой, а что ещё-то?
Казалось бы, если закрыть глаза на неопределённость приоритетов и ввести «натянутую формулировку», то рекурсия должна работать: ведь даже в обсуждении проблем с приоритетами предполагалось, что она работает. В ней-то где ошибка?
Дело в том, что рекурсивное решение этой задачи основывается на том, что туземцы как бы пытаются вычислить то, что думают другие туземцы, о том, что думают третьи туземцы и так далее.
Однако есть тонкий нюанс, внимание!
Для того чтобы человек понял, какого цвета у него глаза, ему достаточно существования какого угодно способа это понять. Он может даже не рассматривать другие — единственного доказательства достаточно.
Но вот при анализе мыслей другого человека уже недостаточно существования хотя бы одного способа вычисления цвета своих глаз, чтобы гарантировать, что именно так этот человек и будет рассуждать. Нужно, чтобы этот способ был ещё и единственным, или хотя бы все существующие способы приводили к ровно тем же выводам. А в данном случае, вдобавок, ровно за то же количество дней.
Поясню на примере.
- Туземец А видел вокруг себя одних только кареглазых, но узнал, что на острове есть голубоглазые. Методом исключения он может вычислить, что он — голубоглазый.
- Туземец А решил проанализировать рассуждения Б и нашёл некий способ рассуждений, при помощи которого Б, скажем, на девятнадцатый день мог бы узнать, что он, Б, — голубоглазый.
В чём тут разница?
Разница в том, что в первом случае А обладает точным знанием о положении вещей.
Во втором же случае он знает лишь один из возможных способов, которым Б мог бы прийти к некоторому выводу. Однако он не знает наверняка, что Б будет идти к этому выводу именно этим способом.
Возможно, Б будет рассуждать как-то иначе и вычислит свой цвет глаз за другое количество дней.
Тогда вся рекурсия посыплется — ведь там всё основано, на привязке количества самоубившихся к порядковому номеру дня. Если же возможна иная привязка, то А будет знать наверняка только какую привязку выбрал он сам, а про выбранную Б привязку будет не точно знать, а лишь предполагать.
Да, мы пока что нашли способ рекурсивного вычисления к двадцатому дню цвета собственных глаз. Но мы ведь не доказали, что нет иных способов — приводящих к такому же ответу на сороковой или, наоборот, на пятый день.
Иными словами, в вышеозвученном рекурсивном решении неявно предполагается, что идеально логичные туземцы неявно предполагают, что каждый из них без какого-либо сговора будет рассуждать одним и тем же способом.
Вдобавок, этот способ ещё и основан на железной уверенности каждого из них, что все остальные тоже рассуждают этим же способом и тоже, в свою очередь, поголовно уверены, что все остальные рассуждают тем же способом.
Но нет, чтобы такое предположение использовать в доказательстве, надо ещё доказать, что все возможные способы рассуждений приводят к одному и тому же выводу, причём в один и тот же день. Только так можно быть железно уверенным в единстве способа рассуждений.
Ну или, в частном случае, достаточно было бы доказать, что существует всего один способ.
Так ли это?
Давайте проверим.
Если голубоглазый туземец всего один, то он сразу же методом исключения поймёт, что он — голубоглазый: ведь известно, что есть голубоглазые, при этом все, кроме него, кареглазые.
Тут существует всего один вариант рассуждений.
Однако давайте взглянем на двух туземцев. Точнее, взглянем на другой возможный вариант их рассуждений.
Туземец А думает:
- Предположим, я, А, — голубоглазый. Как тогда будет рассуждать Б? Например, так.
- Предположим, я, Б, — кареглазый. Тогда голубоглазый А методом исключения вычислит, что он — голубоглазый, и покончит с собой на следующий день. Если же этого не произойдёт, я пойму, что я тоже голубоглазый и покончу с собой на второй день.
- Если Б покончит с собой на второй день, то я, А, пойму, что я — голубоглазый. И покончу с собой на третий день.
Заметьте, этот вариант тоже приводит А к однозначному установлению цвета своих глаз. Равно как и тот, который рассматривался в решении ранее. Однако в этом варианте А покончит с собой только на третий день, а не на второй.
Условие соблюдено: если А может вычислить свой цвет глаз, то он его вычисляет. Но в постановке задаче ведь не говорится, что он должен вычислить это максимально быстрым способом. Да, он мог бы вычислить это и на второй день тоже — предположив свою кареглазость и убедившись на опыте, что это не так. Однако ничто в условиях не обязывает его поступить именно так.
При этом А не находится в каком-то выделенном положении: Б ведь мог бы рассуждать ровно так же, как и А, и А об этом знает.
И А должен учесть такую возможность в своих рассуждениях:
- Предположим, я, А, — голубоглазый. Как тогда будет рассуждать Б? Например, так.
- Предположим, я, Б, — голубоглазый. Как бы тогда рассуждал А?
- Предположим, я, А, — кареглазый. Тогда голубоглазый Б методом исключения вычислит, что он — голубоглазый, и покончит с собой на следующий день. Если же этого не произойдёт, я пойму, что я тоже голубоглазый и покончу с собой на второй день.
- Если А не покончит с собой на второй день, то я, Б, пойму, что я — голубоглазый. И покончу с собой на третий день.
- Если Б покончит с собой на третий день, то я, А, пойму, что я — голубоглазый и покончу с собой на четвёртый день.
Этот процесс — с включением в цепочку ещё одного предположения о голубоглазости, приписываемого другому в модели его рассуждений, — можно продолжать сколько угодно раз, всё дальше и дальше откладывая день полной ясности.
Однако самое главное тут, что ни А, ни Б, не могут точно знать, какой из бесконечного количества этих вариантов выберет другой. И при этом А точно знает, что Б не может знать точно, какой вариант выберет А, а Б точно знает, что А не может точно знать, какой вариант выберет Б.
Разумеется, аналогично будет и при большем количестве голубоглазых — они никогда не покончат с собой, поскольку никогда не будут
точно знать, какой из вариантов рассуждений выбрали другие островитяне.
В таком виде рекурсия лишь могла бы работать, если бы было точно известно, что все рассуждают абсолютно одинаково, но этого нет в условиях задачи, поэтому она не работает.
Подвох в рекурсии
Где-то между строк рекурсивного метода затерялось неявное приравнивание «знания» и «предположения о ходе рассуждений другого». При наличии же нескольких вариантов рассуждений, дающих тот же вывод о цвете своих глаз, но за разное время, предположение о выбранном варианте остаётся лишь предположением: его нельзя считать точным знанием А о мыслительной модели Б — на том лишь основании, что А известен один из возможных вариантов того, как мог бы рассуждать Б.
Чтобы островитяне знали точно варианты рассуждения друг друга, в постановку задачи следовало бы внести что-то вроде: «все туземцы, если есть такая возможность, обязаны вычислить цвет своих глаз максимально быстро и точно знают, что все остальные туземцы делают так же и точно знают всё это про всех остальных туземцев».
В такой формулировке всё население острова как бы начинает стремиться к массовому самоубийству при первом же к тому поводе.
И вот про неё, такую формулировку, видимо, уже можно доказать, что наискорейший способ выяснения цвета своих глаз всего один.
Две ошибки
Итого, красивое решение красивой задачи содержит минимум две ошибки: неопределённость в приоритетах правил и неверное предположение о том, что вариант рассуждений всего один, а потому его можно считать «точным знанием».
В результате, к условию задачи следует добавить ещё два положения:
- Островитяне не могут сообщать другим цвет их глаз, кроме как путём своего самоубийства.
- Все островитяне, если есть такая возможность, обязаны вычислить цвет своих глаз максимально быстро и точно знают, что все остальные островитяне делают так же и точно знают всё это про всех остальных островитян.
Разумеется, с такими дополнениями ситуация на острове становится совсем какой-то уж заведомо суицидальной, что разрушает всю художественность повествования.
Поэтому имело бы смысл превратить эту формулировку в более правдоподобный и одновременно с тем корректный вариант. Благо, она тоже встречается, причём иногда её тень проскальзывает даже в варианте с островитянами.
Мудрецы в колпаках
Султан как-то раз решил испытать своих мудрецов. Он сказал:
«На каждого из вас наденут синий или красный колпак и запрут каждого в своей комнате.
После этого каждому из вас скажут, на ком какого цвета колпак, но какой на вас не скажут. И посмотреть на него вы тоже не сможете.
К каждому из вас в полдень будет приходить стражник, которому вы можете сказать, какого цвета на вас колпак. Если хоть кто-то ошибётся, то всех вас казнят. Того же, кто угадает цвет своего колпака, отпустят.
Стражник ежедневно будет сообщать каждому из вас, казнили ли уже кого-то или, наоборот, отпустили.
Даю вам десять минут, чтобы попрощаться друг с другом, на тот случай, если кто-то из вас не угадает».
Могут ли мудрецы за эти десять минут придумать план освобождения, исключающий риск массовой их казни?
Вот тут, да, рекурсивный метод правда сработает, поскольку мудрецы могут договориться о едином способе рассуждений.
Впрочем, у них есть и более простой и понятный алгоритм:
- Если никого пока что не отпустили, то каждый должен помнить количество красных колпаков — N, о которых ему сообщили, и в день под номером N сказать, что на нём красный колпак.
- Если же мудрец узнал, что кого-то уже отпустили, он должен сказать, что на нём синий колпак.
Почему это работает? Мудрецы в красных колпаках знают об N красных колпаках, те же, на ком синий, — о N+1 красном колпаке. Соответственно, при таком алгоритме есть гарантия, что мудрецы в синем колпаке заявят о цвете своего колпака позже, чем мудрецы в красном. В день N все мудрецы в красных колпаках будут точно знать, что никто не знал о меньшем количестве красных колпаков, чем каждый из них — иначе об этом бы уже сказали. Мудрецы же в синих колпаках будут точно знать, что на них синий, поскольку все мудрецы в красном уже отпущены.
Мудрецы в колпаках без права на переговоры
Теперь предположим, что султан не дал мудрецам возможности посовещаться, а сразу запустил процесс.
В этом случае ситуация становится гораздо менее надёжной. Однако каждый мудрец знает, что другие мудрецы не желают быть казнёнными и хотели бы выйти как можно быстрее. Поэтому каждый из них мог бы предположить, что все остальные выберут наискорейший вариант безопасного вычисления цвета своего колпака: либо с рекурсивными рассуждениями, как в задаче про островитян, либо в виде «упрощённого алгоритма», как в предыдущем разделе.
Правда, эти алгоритмы предполагают выбор цвета, для которого будет использоваться алгоритм, выделенный цвет же султаном не был заявлен, а договориться мудрецам не дали.
Тут каждому мудрецу можно предположить, что все остальные мудрецы догадаются, что лучше бы выйти побыстрее, поэтому следует выбрать для алгоритма тот цвет, которому соответствует меньше половины известных тебе колпаков, если такое возможно.
То есть, если ты знаешь, что мудрецов — сто, а красных колпаков — двадцать, то быстрее всего можно выйти, если в алгоритм подставить красные колпаки. И все остальные, видимо, об этом догадаются, поскольку они тоже знают либо о двадцати, либо о двадцати одном, либо о девятнадцати красных колпаках.
Проблема наступает тогда, когда синих и красных колпаков примерно половина плюс—минус один.
Тут уже придётся, видимо, искать какую-то иную зацепку, вероятность нахождения которой высока и для других мудрецов тоже. Из очевидных же зацепок тут только то, что султан сказал «красные и синие колпаки» — именно в таком порядке. То есть надо выбрать красный, надеясь, что и остальные тоже ухватятся за эту единственную зацепку.
Однако все эти рассуждения, надо отметить, приводят не к гарантированному вычислению цвета своего колпака и всеобщему выживанию, а лишь к наиболее вероятному — точной уверенности нет, но есть обоснованная надежда, что другие мудрецы пойдут именно этим маршрутом, поскольку у всех них общие цели: выйти на свободу как можно быстрее и как можно сильнее снизить риск массовой казни.
В чём же отличие от ситуации с островитянами?
Мудрецы не хотят умирать и островитяне, видимо, тоже, однако отличие между ними в том, что те условия, которые позволяют мудрецам сохранить жизнь, напротив, приводят к смерти островитян.
Островитяне, если есть такая возможность, должны были бы стараться оттянуть свою смерть на как можно более дальний срок, что приводило бы к закономерной неопределённости относительно рассуждений других.
Мудрецы же, даже если им не дали договориться, всё-таки имеют некоторую определённость: ведь кратчайший путь рассуждений выгоден для всех них.
Кроме того, на мудрецов не наложены никакие табу по поводу раскрытия цвета колпака на другом мудреце — им просто физически отрезана возможность передать эту информацию иначе, нежели путём своего освобождения в какой-то день.
Однако запрета на это нет, что тоже снимает целый ряд неопределённостей, которым была посвящена изрядная часть статьи.
Иными словами, рекурсивный алгоритм в такой постановке задачи становится совершенно верным.
Хотя и не таким шокирующим, а потому не так сильно поражающим.
Автор рисунка — Александра «Renoire» Алексеева
