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

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

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

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

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

Ответ

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

${\displaystyle {\frac {k-1}{n}}\leq x_{i}<{\frac {k}{n}}}$,

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

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

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

${\displaystyle x_{1}}$	0.029
${\displaystyle x_{2}}$	0.971
${\displaystyle x_{3}}$	0.423
${\displaystyle x_{4}}$	0.71
${\displaystyle x_{5}}$	0.27
${\displaystyle x_{6}}$	0.542
${\displaystyle x_{7}}$	0.852
${\displaystyle x_{8}}$	0.172
${\displaystyle x_{9}}$	0.62
${\displaystyle x_{10}}$	0.355
${\displaystyle x_{11}}$	0.777
${\displaystyle x_{12}}$	0.1
${\displaystyle x_{13}}$	0.485
${\displaystyle x_{14}}$	0.905
${\displaystyle x_{15}}$	0.218
${\displaystyle x_{16}}$	0.667
${\displaystyle x_{17}}$	0.324

История

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

Примечания

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.
3. Задачи № 6 и 7 в Штейнгауз Г. Сто задач. — М.: Наука, 1976. — 168 с.

Ссылки

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