Всесиб 2022, отборочный этап, 8 класс, задача 5
( баллов) На столе по кругу лежит одинаковых монет, которые могут располагаться либо вверх орлом, либо вверх решкой. Если рядом с некоторой монетой лежат два орла или две решки, то эту монету можно перевернуть. Такую операцию разрешается проделать неограниченное число раз. При каких можно вне зависимости от начального положения монет перевернуть их все одной стороной вверх?
Ответ
Решение. Пусть нечётно. Разделим весь круг на группы из одинаковых подряд идущих монет. Найдётся группа из нечётного числа монет (иначе общее количество монет в круге будет чётным как сумма чётных чисел). Рассмотрим эту группу. Перевернём в ней вторую, четвёртую и т. д. — все чётные монеты. После этого мы сможем перевернуть в ней первую, третью и т. д. — все нечётные монеты. В итоге количество групп в круге уменьшится, и мы сможем повторить все те же самые рассуждения. В конце концов группа останется только одна, но это и будет значить, что все монеты перевёрнуты одинаково.
Теперь пусть чётно. Если делится на , то в расстановке нельзя сделать вообще ни одной операции. Если не делится, то рассмотрим расстановку — одна группа из четырёх решек, а остальные группы по орла или решки. Если мы перевернём вторую решку из этих четырёх, то после этого мы можем перевернуть только первую, и получить аналогичную расстановку, в которой орла. Если перевернём третью, то затем только четвёртую, и снова орла. Для этой расстановки аналогичными рассуждениями можно показать, что мы можем получить только расстановку, которая была изначально (или сдвинуть эту группу из решек). Значит, перевернуть все монеты одной стороной не выйдет.