Задача
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– разной "длины". По предположению индукции отсюда следует существование.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь