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

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

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

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

Для каких [math]\displaystyle{ N }[/math] можно построить такую последовательность [math]\displaystyle{ x_1, x_2, ... , x_N }[/math]?

Ответ

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

[math]\displaystyle{ \frac{k-1}{n} \le x_i \lt \frac{k}{n} }[/math],

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

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

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

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

Ссылки

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