Одна из увлекательных тем кружковой и олимпиадной математики - "переаттестация мудрецов". Эта серия головоломок, которые начинаются примерно с таких слов:
В некотором царстве король устроил своим придворным мудрецам переаттестацию. Он объявил им правила испытания и дал сутки на обдумывание решения. Сегодня вы - мудрецы. Докажите королю свою профпригодность!
Такие задачи встречаются не только на олимпиадах, но и на собеседованиях в крупные компании, что неудивительно: с их помощью проверяют, насколько у кандидата развита смекалка, креативные способности, умение анализировать информацию - и всё это за ограниченное время. Впрочем, этих качеств может оказаться недостаточно - в задачах потруднее нужна кое-какая математика. Подобные задачи "приглашают" познакомиться с такими разделам математики, как теория игр, теории информации, эпистемика (раздел модальной логики о состояниях познания).
Мы рассмотрим серию задач, в которых мудрецам нужно отгадать цвета колпаков, которые на них надели. Начнём с совсем простого испытания и затем будем его усложнять и развивать.
Задача 0. На каждого из двух мудрецов надевают колпак одного из двух цветов: белый или чёрный (возможны 4 варианта). Каждый мудрец видит колпак товарища, но не видит свой. Король спрашивает любого мудреца, какой на нём колпак, и тот выкрикивает один из цветов: белый или чёрный (второй мудрец это слышит). Затем король обращается с тем же вопросом к другому мудрецу, и тот пытается отгадать свой цвет. Испытание пройдено, если максимум один мудрец ошибся. Как мудрецам заранее, до испытания, договориться, чтобы гарантированно один из них угадал свой цвет?