Олимпиадная задача: 101 мудрец по кругу, смена мнений и инварианты, 9-10 класс
Задача
По кругу стоит 101 мудрец. Каждый из них либо считает, что Земля вращается вокруг Юпитера, либо считает, что Юпитер вращается вокруг Земли. Один раз в минуту все мудрецы одновременно оглашают свои мнения. Сразу после этого каждый мудрец, оба соседа которого думают иначе, чем он, меняет своё мнение, а остальные – не меняют. Докажите, что через некоторое время мнения перестанут меняться.
Решение
Сопоставим каждому мудрецу с некоторым мнением знак "+", а с противоположным – знак "–". Тогда расстановке мудрецов соответствует расстановка 101 знака по кругу.
Пусть в некоторый момент два одинаковых знака стоят подряд. Тогда в следующую минуту они не изменятся, и поэтому останутся одинаковыми. Значит, ни в один из последующих моментов они также не изменятся.
Назовём знак стабильным, если рядом с ним стоит хотя бы один такой же. Поскольку количество знаков нечётно, стабильный знак найдётся. Кроме того, любой стабильный знак уже не изменяется и остаётся стабильным, а любой нестабильный знак в очередную минуту меняется на противоположный. Если в какой-то момент не все знаки стабильны, то найдётся стабильный знак a, соседний с нестабильным знаком b. В следующую минуту a не изменится, а b изменится, то есть станет таким же, как a и, следовательно, стабильным.
Итак, пока нестабильные знаки есть, их количество строго уменьшается. Значит, рано или поздно оно станет равным нулю, и перемены знаков закончатся.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь