|
|
 |
Условие
k вершин правильного n-угольника закрашены. Закраска называется почти равномерной, если для любого натурального m верно следующее условие: если M1 – множество m расположенных подряд вершин и M2 – другое такое множество, то количество закрашенных вершин в M1 отличается от количества закрашенных вершин в M2 не больше чем на 1. Доказать, что для любых натуральных n и k ≤ n почти равномерная закраска существует и что она единственна с точностью до поворотов закрашенного множества.
Решение
1) Индукция по n. База (n = 2) очевидна.
Шаг индукции. Предположим, что утверждение доказано для правильных многоугольников с количеством вершин, меньших n.
Для k = 1 утверждение очевидно. Закрашенные (красные) вершины можно поменять местами с незакрашенными. Поэтому далее считаем, что
1 < k ≤ n/2.
Разделим n на k с остатком: n = kq + r. Назовём дыркой множество из неокрашенных точек, находящихся между красными. Заметим, что в дырке не менее
q – 1 точки. Действительно, если это не так, можно выделить k непересекающихся q-групп (групп из q последовательных вершин), в одной из которых две красные точки. В остальных, в силу равномерности, красных точек не менее одной, и всего красных точек больше k. Противоречие.
С другой стороны, найдётся дырка из q – 1 точки (в противном случае всего точек не меньше чем k + kq > n) . Следовательно, нет дырок из более чем q точек (иначе есть группа из q + 1 вершины без красных точек и другая группа с двумя красными точками).
Итак, дырки могут быть двух сортов – из q – 1 и q точек. Смоделируем схему дырок на правильном k-угольнике, окрасив в синий цвет вершины, соответствующие дыркам из q точек.
2) Если исходная закраска была правильная, то и полученная – правильная. Действительно, предположим противное: есть две l-группы P и Q из вершин k-угольника, причем в Q ровно на две синие точки больше (в силу дискретной непрерывности все промежуточные значения принимаются). В исходном n-угольнике к прообразам этих l-групп добавим разделяющие дырки точки. Мы получим две группы вершин P1 и Q1 с одинаковым количеством красных точек, но всего точек в Q1 на две больше, чем в P1. Добавив с двух сторон к P1 по точке (а обе они красные), получим две группы из равного числа точек, но с количеством красных точек, отличающимся на 2. Противоречие.
3) Обратно, если полученная закраска правильная, то и исходная была правильная.
Действительно, пусть P и Q – две группы вершин n-угольника, причём в P – m, а в Q не менее m + 2 красных точек. Тогда Q содержит по крайней мере m + 1 дырку, то есть её "длина" не меньше m(q – 1) + s + m + 2, где s – количество соответствующим этим дыркам синих точек.
P же содержит не более k + 1 дырки (две на краях, возможно, неполные) и (поскольку количество соответствующих синих точек не больше s + 1) её "длина" не превосходит m(q – 1) + (s + 1) + m. Поэтому P и Q – разной "длины".
По предположению индукции отсюда следует существование.
Замечания
1. Задача предлагалась в "трудном" варианте второго тура.
2. 30 баллов.
3. Ср. с задачей М818 из Задачника "Кванта".
