Олимпиадная задача о переаттестации Совета Мудрецов: минимизация казней
Задача
Переаттестация Совета Мудрецов происходит так: король выстраивает их в колонну по одному и надевает каждому колпак белого, синего или красного цветов. Все мудрецы видят цвета всех колпаков впереди стоящих мудрецов, а цвет своего и всех стоящих сзади не видят. Раз в минуту один из мудрецов должен выкрикнуть один из трёх цветов (каждый мудрец выкрикивает цвет один раз).
После окончания этого процесса король казнит каждого мудреца, выкрикнувшего цвет, отличный от цвета его колпака.
Накануне переаттестации все сто членов Совета Мудрецов договорились и придумали, как минимизировать число казненных. Скольким из них гарантированно удастся избежать казни?
Решение
Все 100 мудрецов гарантированно спастись не могут, поскольку цвет колпака у последнего мудреца никто из них не видит.
Покажем, как можно спасти 99 мудрецов. Белому, синему и красному цветам сопоставим числа 0, 1 и 2 соответственно. В первую минуту мудрец, стоящий позади всех, должен выкрикнуть цвет, соответствующий остатку от деления на 3 суммы всех чисел, сопоставленных цветам колпаков мудрецов, стоящих впереди.
Тогда мудрец, стоящий непосредственно перед ним, сможет вычислить цвет своего колпака, так как видит колпаки всех 98 мудрецов, стоящих впереди; этот цвет он и должен выкрикнуть во вторую минуту.
В третью минуту мудрец, стоящий в колонне 98-м, вычисляет, основываясь на информации, полученной из двух предыдущих выкриков и видя колпаки 97 стоящих впереди, цвет своего колпака, выкрикивает его, и т.д.
Ответ
99 мудрецов.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь