Задача о 18 точках

Материал из Википедии — свободной энциклопедии

Задача о 18 точках (парадокс 18 точек) — одна из задач вычислительной геометрии.

Поместим на отрезок точку с номером 1. Затем добавим ещё одну с номером 2 таким образом, чтобы они оказались в разных половинах отрезка. Третью точку добавим таким образом, чтобы все три находились в разных третях отрезка. Далее, для точки с номером $N$ должно выполняться условие, что все точки от первой до $N$ -й находились в различных частях отрезка длиной не более $1 / N$ его общей длины. С точки зрения интуиции кажется, что должна существовать последовательность вещественных чисел $x 1, x 2,..., x N$ , такая что для каждого целого $n = 1.. N$ и каждого целого $k = 1.. n$ выполняется уравнение

$\frac{k-1}{n} \le x_i < \frac{k}{n}$ ,

где $i = 1.. n$ . Однако, доказано^[1], что таким образом можно поместить на отрезок максимум 17 точек, причём количество таких сочетаний ограничено и равно 768^[2].

[править] Примечания

↑ 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.