Олимпиадная задача Фомина Д.: Круг, фишки и инварианты — задача по олимпиадной математике для 7-9 классов
Круг разбит на n секторов, в некоторых секторах стоят фишки – всего фишек n + 1. Затем позиция подвергается преобразованиям. Один шаг преобразования состоит в следующем: берутся какие-нибудь две фишки, стоящие в одном секторе, и переставляются в разные стороны в соседние секторы. Докажите, что через некоторое число шагов не менее половины секторов будет занято.
Разобрать решение
Поскольку фишек больше чем секторов, то в любой момент в каком-то секторе будут находиться не менее двух фишек. Значит, движение продолжается бесконечно долго.
Занумеруем все секторы, начиная с данного, числами 1, ..., n в порядке их обхода по часовой стрелке. Для каждой фишки вычислим квадрат номера её сектора. Пусть S – сумма этих квадратов. Если сектор 1 все время пуст, то S с каждым ходом увеличивается: при ходе из сектора k (k < n) к S добавляется
(k + 1)² + (k – 1)² – 2k² = 2. С другой стороны, S ≤ (n + 1)n². Противоречие.
Значит, когда-то в сектор 1 попадёт фишка. После этого всегда либо сектор 1, либо сектор 2 будет непустым: всякий раз, когда освобождается один из них, второй заполняется.
Поскольку все секторы равноправны, наступит момент, когда все они побывают заполненными. После этого, как показано выше, оба соседа каждого пустого сектора непусты. Поэтому пустых секторов будет не больше чем непустых.
Обсуждение
0Комментариев пока нет.