|
|
 |
Условие
На окружности длины 2013 отмечены 2013 точек, делящих её на равные дуги. В каждой отмеченной точке стоит фишка. Назовём расстоянием между двумя точками длину меньшей дуги между ними. При каком наибольшем n можно переставить фишки так, чтобы снова в каждой отмеченной точке было по фишке, а расстояние между любыми двумя фишками, изначально удалёнными не более чем на n, увеличилось?
Решение
Оценка. Занумеруем точки и стоящие на них фишки по часовой стрелке последовательными неотрицательными целыми числами от 0 до 2012. Рассмотрим произвольную перестановку и фишки с номерами 0, 671 и 1342, изначально расположенные в вершинах правильного треугольника. Попарные расстояния между ними равны 671. После перестановки сумма попарных расстояний между этими фишками не будет превосходить длины окружности, а значит, расстояние между какими-то двумя не будет превосходить 2013 : 3 = 671; поэтому расстояние между этими двумя фишками не увеличится. Итак, при n ≥ 671 требуемая перестановка невозможна.
Пример искомой перестановки для n = 670. Каждую фишку с номером i ≤ 1006 переставим в точку с номером ai = 2i, а каждую фишку с номером
i ≥ 1007 – в точку с номером
ai = 2i – 2013. Иначе говоря, ai – это остаток от деления 2i на 2013. Нетрудно понять, что в каждую точку попало по фишке. Осталось показать, что расстояния между парами фишек, изначально удалённых друг от друга не более чем на 670, при этом возрастут.
Рассмотрим произвольные фишки с номерами i и j; пусть расстояние между ними равно d ≤ 670. Тогда одна из дуг между точками ai и aj будет иметь длину 2d, то есть расстояние между этими точками есть d' = min {2d, 2013 – 2d}. Но заметим, что
2d > d и 2013 – 2d > d .
Значит, и d' > d, что и требовалось.
Ответ
n = 670.
