ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 116759
Темы:    [ Процессы и операции ]
[ Полуинварианты ]
[ Четность и нечетность ]
Сложность: 3
Классы: 9,10
В корзину
Прислать комментарий

Условие

По кругу стоит 101 мудрец. Каждый из них либо считает, что Земля вращается вокруг Юпитера, либо считает, что Юпитер вращается вокруг Земли. Один раз в минуту все мудрецы одновременно оглашают свои мнения. Сразу после этого каждый мудрец, оба соседа которого думают иначе, чем он, меняет своё мнение, а остальные – не меняют. Докажите, что через некоторое время мнения перестанут меняться.


Решение

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

Замечания

Можно показать, что знаки могут изменяться в течение лишь первых 50 минут.

Источники и прецеденты использования

олимпиада
Название Всероссийская олимпиада по математике
год
Год 2011-2012
Этап
Вариант 5
класс
Класс 9
Задача
Номер 9.5
олимпиада
Название Всероссийская олимпиада по математике
год
Год 2011-2012
Этап
Вариант 5
класс
Класс 10
Задача
Номер 10.5

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .