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

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

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

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

Для каких $N$ можно построить такую последовательность $x_{1},x_{2},...,x_{N}$?

Ответ

Может показаться, что каждого целого $N\geq 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}}\leq 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$.

Ссылки

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