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

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

Формулировка

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

Для каких $N$ можно построить такую последовательность $x_1,x_2,...,x_N$?

Ответ

Может показаться, что каждого целого $N\ge 1$ должна существовать такая последовательность вещественных чисел $x_1,x_2,...,x_N$. То есть такая, что для каждого целого $n\in \{1,\dots ,N\}$ и каждого целого $k\in \{1,\dots ,n\}$ найдётся такое $i\in \{1,\dots ,n\}$, что выполняется неравенство

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

Однако, доказано, что таким образом можно поместить на отрезок максимум 17 точек, причём число различных порядков ограничено и равно 768.

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

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

$x_1$	0.029
$x_2$	0.971
$x_3$	0.423
$x_4$	0.71
$x_5$	0.27
$x_6$	0.542
$x_7$	0.852
$x_8$	0.172
$x_9$	0.62
$x_{10}$	0.355
$x_{11}$	0.777
$x_{12}$	0.1
$x_{13}$	0.485
$x_{14}$	0.905
$x_{15}$	0.218
$x_{16}$	0.667
$x_{17}$	0.324

История

Эта задача обсуждается в задачнике Гуго Штейнгауза 1964 года. Однако там приводятся только оценки — найдено решение для $N=14$ и приводится доказательство Анджея Шинцеля, что задача неразрешима при $N=75$.

Ссылки

• Шаблон:MathWorld