Задача о 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].

Одно из 768 возможных решений:

$x_{14}$	0.05
$x_{4}$	0.075
$x_{7}$	0.15
$x_{11}$	0.22
$x_{2}$	0.29
$x_{16}$	0.33
$x_{9}$	0.38
$x_{6}$	0.46
$x_{13}$	0.51
$x_{1}$	0.58
$x_{17}$	0.6
$x_{10}$	0.65
$x_{5}$	0.73
$x_{15}$	0.77
$x_{8}$	0.83
$x_{12}$	0.9
$x_{3}$	0.95

Примечания

1. ↑ Berlekamp, E. R. и Graham, R. L. Irregularities in the Distributions of Finite Sequences. — 1970. — С. 152-161.
2. ↑ Warmus, M. A Supplementary Note on the Irregularities of Distributions. — 1976. — С. 260-263.

Ссылки

• Weisstein, Eric W. 18-Point Problem (англ.) на сайте Wolfram MathWorld.