|
|
 |
Условие
Числа от 1 до 1000 расставлены по окружности.
Доказать, что их можно соединить 500 непересекающимися отрезками, разность чисел на концах которых (по модулю) не более 749.
Решение
Покрасим точки с номерами от 251 до 750 включительно в красный цвет, а остальные – в синий. Заметим, что наибольшая разность между номерами синей и красных точек равна 1000 – 251 = 750 – 1 = 749.
Соединим отрезком соседние разноцветные точки (такие, очевидно, есть). Временно удалим их и снова соединим соседние разноцветные точки. Продолжим эту процедуру, пока все точки не будут соединены. Восстановив удалённые точки и отрезки, получим систему непересекающихся отрезков, удовлетворяющую условиям задачи.
Замечания
1. Мы воспользовались тем, что все точки стоят в вершинах выпуклого многоугольника. Но верно и более общее утверждение – см. задачу 55228.
2. 12 баллов.
