Задача о 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}}}$ ,

Однако, доказано , что таким образом можно поместить на отрезок максимум 17 точек, причём число различных порядков ограничено и равно 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 года. Однако там приводятся только оценки — найдено решение для ${\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. (англ.) на сайте Wolfram MathWorld .