Условие
Какое наименьшее число точек можно выбрать на окружности длины 1956 так,
чтобы для каждой из этих точек нашлась ровно одна выбранная точка на расстоянии
1 и ровно одна на расстоянии 2 (расстояния измеряются по окружности)?
Решение
Ответ: 1304.
Пусть
A — одна из выбранных точек,
B и
C — выбранные точки, удалённые
от неё на расстояния 1 и 2 соответственно. Расположение в порядке
ABC
невозможно, поскольку в таком случае для точки
B есть две выбранные точки на
расстоянии 1. Поэтому точки расположены в таком порядке:
C AB (или
BA C). Пусть
D — точка, удалённая от
C на расстояние 1.
Расположение
CDAB, очевидно, невозможно. Поэтому расположение такое:
DC AB. Пусть, далее,
E — точка, удалённая от
B на расстояние 1.
Она расположена следующим образом:
DC AB E. Продолжая эти
рассуждения, мы увидим, что окружность длины 1956 окажется разбитой на
1956/3 = 652 дуги длины 3 (концами этих дуг служат точки
A,
C,
E,
...). На каждой дуге лежит одна точка. Всего получаем
2
. 652 = 1304
точки. Все эти точки обязательно должны присутствовать.
Источники и прецеденты использования
