- Задача о 18 точках
-
Задача о 18 точках (парадокс 18 точек) — одна из задач вычислительной геометрии.
Поместим на отрезок точку с номером 1. Затем добавим ещё одну с номером 2 таким образом, чтобы они оказались в разных половинах отрезка. Третью точку добавим таким образом, чтобы все три находились в разных третях отрезка. Далее, для точки с номером должно выполняться условие, что все точки от первой до -й находились в различных частях отрезка длиной не более его общей длины. С точки зрения интуиции кажется, что должна существовать последовательность вещественных чисел , такая, что для каждого целого и каждого целого выполняется неравенство
- ,
где . Однако, доказано[1], что таким образом можно поместить на отрезок максимум 17 точек, причём количество таких сочетаний ограничено и равно 768[2].
Одно из 768 возможных решений:
0.05 0.075 0.15 0.22 0.29 0.33 0.38 0.46 0.51 0.58 0.6 0.65 0.73 0.77 0.83 0.9 0.95 Примечания
- ↑ Berlekamp, E. R. и Graham, R. L. Irregularities in the Distributions of Finite Sequences. — 1970. — С. 152-161.
- ↑ Warmus, M. A Supplementary Note on the Irregularities of Distributions. — 1976. — С. 260-263.
Ссылки
- Weisstein, Eric W. 18-Point Problem (англ.) на сайте Wolfram MathWorld.
Категории:- Вычислительная геометрия
- Комбинаторная геометрия
Wikimedia Foundation. 2010.