Парадокс 18 точек

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

Поместим на отрезок точку с номером 1. Затем добавим ещё одну с номером 2 таким образом, чтобы они оказались в разных половинах отрезка. Третью точку добавим таким образом, чтобы все три находились в разных третях отрезка. Далее, для точки с номером N должно выполняться условие, что все точки от первой до N-й находились в различных частях отрезка длиной не более 1 / N его общей длины. С точки зрения интуиции кажется, что должна существовать последовательность вещественных чисел x₁,x₂,...,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 возможных решений:

x14	0.05
x4	0.075
x7	0.15
x11	0.22
x2	0.29
x16	0.33
x9	0.38
x6	0.46
x13	0.51
x1	0.58
x17	0.6
x10	0.65
x5	0.73
x15	0.77
x8	0.83
x12	0.9
x3	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.(англ.)