Мудрецы и шляпы

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

В этой задаче у мудрецов, помимо возможности назвать цвет, появляется возможность сказать «пас». Они должны использовать эту возможность не просто так, а для передачи информации. Попробуйте понять, в какой ситуации один мудрец должен спасовать, а следующий при этом точно сможет назвать свой цвет?

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

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

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

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

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

Заметим, что как только кто-то из мудрецов правильно назовет свой цвет, условия султана будут выполнены, и остальные могут просто спасовать.

Мудрецы могут действовать следующим образом. Опять они будут отвечать по очереди, начиная с конца ряда. Слово «пас» каждый мудрец может использовать, чтобы сообщить остальным, что перед ним есть не только желтые шляпы. Если перед каким-то из мудрецов все спасовали, а он видит перед собой только желтые шляпы, то он точно знает, что его шляпа синяя, и может назвать ее цвет. Это верно и для первого в ряду — мудреца, который вообще никого не видит: если до него были только «пасы», то он точно знает, что его шляпа синяя (а если его шляпа желтая, то кто-то из предыдущих уже должен был назвать синий цвет). Мудрец А, который отвечает первым, действует аналогично: пасует, если видит перед собой не только желтый цвет и говорит «синий», если видит только желтые шляпы.

Эта стратегия приводит мудрецов к успеху во всех случаях, кроме одного — когда все шляпы желтые. Пусть, для примера, мудрецов 10. Тогда существуют \(2^{10} = 1024\) способа раздать им шляпы двух цветов (поскольку 10 раз надо сделать выбор из двух опций). Значит, вероятность остаться при дворе равна \(\frac{1023}{1024}\). Если мудрецов \(n\), то вероятность успеха равна \(\frac{2^n-1}{2^n}\).

Задачи про мудрецов и шляпы, подобные рассмотренным выше, — очень популярный тип задач на логику и поиск кооперативной стратегии. Судя по тому, что они регулярно «гуляют» по социальным сетям и сайтам с головоломками, они обладают изрядной виральностью. Вероятно, это вызвано или их обманчивой простотой, или, наоборот, кажущейся парадоксальностью (ведь во многих таких задачах сначала кажется, что никакой стратегии лучше случайного угадывания быть не может).

На «Элементах» задачи на кооперацию уже разбирались. Например, в задаче Сто шляп предлагается следующий вариант. Сотню испытуемых выстраивают в круг (так что каждый видит всех остальных) и надевают на голову шляпы с числами от 1 до 100 (числа могут повторяться; это равносильно тому, что шляпы могут иметь любой цвет из ста разных цветов). Хотя бы один из испытуемых должен верно назвать свое число. Учитывая, что числа выбираются абсолютно случайно и могут повторяться, кажется, что здесь-то уж точно нет никакой разумной стратегии и нужно просто гадать. Но нет, оказывается, что и в этой ситуации испытуемые могут гарантировать себе успех! Очень рекомендую пройти по ссылке и почитать решение — там подробно разобран процесс размышлений, который приводит к правильной стратегии.

Еще один очень известный пример задачи на кооперацию — задача о заключенных и выключателе:

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

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

1. Пусть в условиях первого вопроса мудрецов бесконечно много (но счетное количество). Они стоят в ряд лицом к затылку, причем все мудрецы смотрят в сторону бесконечного «хвоста» этого ряда. Таким образом, каждый видит цвета шляп бесконечного числа мудрецов перед ним. Мудрецы должны по очереди называть цвет своих шляп — кто не угадает, тот будет сослан. Как им действовать, чтобы минимизировать число сосланных.

Интересно, что и в этом случае они могут добиться того, чтобы все, кроме самого первого, гарантированно правильно назвали свой цвет. Внезапно, для этого приходится привлечь аксиому выбора (все-таки, мы имеем дело с бесконечным множеством). Если кратко, то идея в следующем. По сути, мы имеем дело с бесконечной в одну сторону последовательностью нулей и единиц (сопоставим желтый цвет нулям, а синий — единицам, например). На множестве таких последовательностей можно ввести отношение эквивалентности: мы считаем две последовательности эквивалентными, если, начиная с некоторого места, они полностью совпадают. Важно, что любые две последовательности из одного класса имеют лишь конечное число различий. Мудрецы должны договориться о том, что из каждого класса эквивалентности будет выбрана одна конкретная последовательность (здесь и нужна аксиома выбора) — так сказать, «название» этого класса.

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

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

Но вернемся к конечным множествам.

2. На этот раз мудрецов всего лишь четверо. На них надели шляпы — 2 белые и 2 черные (мудрецы знают об этом). Затем их выстроили в ряд, так что цвета шляп чередуются (см. рисунок). При этом один из мудрецов стоит за стенкой — он не видит остальных, а они не видят его. Крутить головой нельзя, поэтому, например, мудрец 2 видит только цвет шляпы на мудреце 3. Нужно, чтобы хотя бы один из мудрецов правильно назвал свой цвет. Ошибаться при этом нельзя, а никакого обмена информацией между мудрецами нет. Через небольшое время один из них смог правильно назвать свой цвет. Кто это был?

Если вы знаете другие примеры подобных задач — делитесь ими в комментариях.