Русская Википедия:Задача о складном метре
Задача о складном метре — это задача комбинаторной геометрии, которую можно сформулировать следующим образом: Шаблон:Начало цитаты Можно ли непересекающуюся цепочку отрезков преобразовать непрерывным движением без пересечения отрезков так, что все вершины цепочки (места сочленения отрезков) будут лежать на одной прямой? Шаблон:Конец цитаты
Тесно связанная задача — показать, что любой простой многоугольник может быть преобразован к выпуклому виду непрерывным преобразованием с сохранением во время движения длин сторон, при этом во всё время движения многоугольник остаётся простым[1].
Обе задачи были успешно решены группой Коннелли, Демейн, РотеШаблон:Sfn.
История
Задача была поставлена в 1970 году Сью Уайтсайдс, и оставалась открытой в течение 30 лет. Несмотря на кажущуюся простоту, задача не имеет элементарного решения.
Чтобы понять тонкость вопроса, вместо «складного метра» рассмотрим «шарнирный механизм, реализующий граф-дерево». Не всякое такое дерево можно распрямить. Так, у графа-паучка нельзя распрямить ноги, избегая самопересечений и оставаясь в плоскости.
Этот паучок какое-то время вдохновлял попытки математиков построить нераспрямляемый складной метр — они пытались построить ломаную, дважды обходящую контур паучка.
Комбинаторное доказательство
После выхода работы Коннелли и др. Илеана Стрейну (Ileana Streinu) опубликовала упрощённое комбинаторное доказательство, сформулированное в терминологии Шаблон:Не переведено 5 руки робота. Как оригинальное доказательство, так и доказательство Стрейну находят непрерывное движение, при котором никакие две точки не двигаются навстречу друг другу. Версия Стрейну доказательства добавляет рёбра к исходной фигуре для образования Шаблон:Не переведено 5, удаляет одно добавленное ребро выпуклой оболочки этого графа и показывает, что оставшийся граф имеет однопараметрическое семейство движений, в которых расстояния не уменьшаются. Если повторно применять эти движения, в конечном счёте, они приведут к положению, в котором никакое расширяющее движение невозможно, что бывает, только когда цепочка вытягивается в линейку или многоугольник становится выпуклым.
Стрейну и УитлиШаблон:Sfn привели приложение этого результата к математике оригами — они описали, каким образом сложить любое одновершинное оригами, используя только непересекающиеся движения бумаги. По существу, этот процесс складывания является обращённой во времени версией задачи преобразования многоугольника в выпуклую форму, но на поверхности сферы, а не на евклидовой плоскости. Этот результат расширили Панина и СтрейнуШаблон:Sfn на сферические многоугольники с длиной ребра, меньшей 2π.
Обобщение
Джон ПардонШаблон:Sfn обобщил задачу о складном метре для спрямляемых кривых. Он показал, что любая спрямляемая жорданова кривая может быть сделана выпуклой без увеличения длины и без уменьшения расстояния между любыми двумя точками кривой. За это исследование, которое он сделал, ещё будучи студентом средней школы, Пардон получил вторую премию 2007 года в соревновании Шаблон:Не переведено 5Шаблон:Sfn.
См. также
- Укорачивающий поток, непрерывное преобразование замкнутой кривой на плоскости, в конце концов приводящее к выпуклой кривой.
Примечания
Литература
- Шаблон:Статья Статья является заметками по лекции в Летней школе «Современная математика» , 2008
- Шаблон:Статья. Предварительная версия на 41-ом ежегодном симпозиуме Foundations of Computer Science, 2000.
- Шаблон:Статья.
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Статья.
- Шаблон:Книга
.svg){kind=link}
.svg){kind=link}