Задача о 18 точках (парадокс 18 точек) — одна из задач вычислительной геометрии.
Формулировка Поместим на отрезок точку с номером 1. Затем добавим ещё одну с номером 2 таким образом, чтобы они оказались в разных половинах отрезка. Третью точку добавим таким образом, чтобы все три находились в разных третях отрезка. Далее, для точки с номером должно выполняться условие, что все точки от первой до -й находились в различных частях отрезка длиной не более его общей длины.
Для каких можно построить такую последовательность ?
Ответ Может показаться, что каждого целого должна существовать такая последовательность вещественных чисел . То есть такая, что для каждого целого и каждого целого найдётся такое , что выполняется неравенство ,
Однако, доказано, что таким образом можно поместить на отрезок максимум 17 точек, причём число различных порядков ограничено и равно 768.
Одно из 768 возможных решений:
0.0290.9710.4230.710.270.5420.8520.1720.620.3550.7770.10.4850.9050.2180.6670.324
История
Эта задача обсуждается в задачнике Гуго Штейнгауза 1964 года.Задачи № 6 и 7 в Однако там приводятся только оценки — найдено решение для и приводится доказательство Анджея Шинцеля, что задача неразрешима при .
Примечания
Ссылки
Категория:Вычислительная геометрия Категория:Комбинаторная геометрия Категория:Математические парадоксы