WikiSort.ru - Не сортированное

Задача о 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 возможных решений:

${\displaystyle x_{14}}$	0.05
${\displaystyle x_{4}}$	0.075
${\displaystyle x_{7}}$	0.15
${\displaystyle x_{11}}$	0.22
${\displaystyle x_{2}}$	0.29
${\displaystyle x_{16}}$	0.33
${\displaystyle x_{9}}$	0.38
${\displaystyle x_{6}}$	0.46
${\displaystyle x_{13}}$	0.51
${\displaystyle x_{1}}$	0.58
${\displaystyle x_{17}}$	0.6
${\displaystyle x_{10}}$	0.65
${\displaystyle x_{5}}$	0.73
${\displaystyle x_{15}}$	0.77
${\displaystyle x_{8}}$	0.83
${\displaystyle x_{12}}$	0.9
${\displaystyle x_{3}}$	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.

Это заготовка статьи по математике. Вы можете помочь проекту, дополнив её.