|
|
 |
Условие
Король решил поощрить группу из $n$ мудрецов. Их поставят в ряд друг за другом (чтобы все смотрели в одном направлении), на каждого наденут чёрную или белую шляпу. Каждый будет видеть шляпы всех впереди стоящих. Мудрецы по очереди (от последнего к первому) назовут цвет (белый или чёрный) и натуральное число по своему выбору. В конце подсчитывается число мудрецов, которые назвали цвет, совпадающий с цветом своей шляпы: ровно столько дней всей группе будут платить надбавку к жалованью. Мудрецам разрешили договориться заранее, как отвечать. При этом мудрецы знают, что ровно $k$ из них безумны (кто именно – им неизвестно). Безумный мудрец называет белый или чёрный цвет и число вне зависимости от договорённостей. Какое максимальное число дней с надбавкой к жалованью могут гарантировать группе мудрецы, независимо от местонахождения безумных в очереди?
Решение
Оценка. $k$ безумцев, очевидно, могут не угадать. Первый говорящий из умных также может не угадать, поскольку у него нет никакой информации о цвете его шляпы. Поэтому больше $n - k - 1$ угадываний гарантировать нельзя.
Алгоритм. Пусть все мудрецы единообразно кодируют раскраску видимых ими шляп. Мудрец, видящий $i$ шляп, называет число от $1$ до $2^i$. Если он назовёт другое число, то пусть все считают, что он назвал единицу. Тогда каждому мудрецу, кроме начинающего, сообщают цвет его шляпы все предыдущие ораторы. Вопрос только в том, кого из них слушаться, чтобы назвать свой цвет.
Назовём начинающего текущим оракулом. Стратегия умного мудреца – называть тот цвет, что указал ему последний оракул. Если говорящий слушается оракула, то он сам становится оракулом, иначе оракул не меняется. Так как все всё слышат, то каждый может проследить за тем, кто сейчас оракул.
Заметим, что каждый из умных будет оракулом. Каждого умного, кроме последнего говорящего из них, кто-нибудь послушается на отрезке до следующего умного включительно. Поэтому будет хотя бы $n - k - 1$ угадываний.
Ответ
$n - k - 1$.
Замечания
12 баллов
