Переаттестация мудрецов

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

В некотором царстве король устроил своим придворным мудрецам переаттестацию. Он объявил им правила испытания и дал сутки на обдумывание решения. Сегодня вы - мудрецы. Докажите королю свою профпригодность!

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

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

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

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

Задача 1. Король позвал всех своих мудрецов, а их у него несколько десятков, и дал ту же задачу. На каждом мудреце либо белый, либо чёрный колпак. Каждый видит всех, кроме себя. Король выбирает мудрецов в случайном порядке, и каждый выкрикивает один из цветов так, что все слышат. Ошибиться может максимум один.

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

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

Задача 2. Король решил усложнить задачу мудрецам. Теперь они должны ответить про цвета колпаков одновременно. Для этого он дал каждому две таблички: белую и чёрную. Сколько теперь мудрецов могут гарантированно угадать свой цвет?

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

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

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

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

Давайте ещё усложним задачу, увеличив количество цветов.

Задача 3. Обобщим задачу 1. Пусть цветов колпаков всего (они заранее известны). Как действовать мудрецам, чтобы ошибся максимум один из них?

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

Задача 4. А теперь обобщим задачу 2. Пусть цветов , а мудрецов . У каждого мудреца таблички тех же цветов, что и цвета колпаков. Мудрецы должны поднять таблички одновременно. Пусть правильно ответившие мудрецы получают по золотой монете. Какое наибольшее число монет мудрецы могут гарантированно выиграть у короля?

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

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

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

Задача 5. Бесконечное (счётное) число мудрецов сидят в ряд. На каждого надели колпак одного из двух цветов: белый, чёрный. Мудрец с номером видит всех перед собой: от до бесконечности, но не видит свой колпак и колпаки мудрецов с меньшими номерами. Мудрецы пытаются отгадать свой цвет. Каждый пишет цвет, который ему кажется, на бумаге. Как договориться мудрецам, чтобы лишь конечное число из них ошиблись.

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

Автор: Андрей Канунников, к. ф.-м. н., мехмат МГУ, преподаватель ШАД Хелпер