Проблема червя Мозера
| 1. | Верхняя граница — диск, диаметр которого равен длине червя. |
| 2. | По симметрии достаточно половины диска. |
| 3. | Крышка должна выдерживать ширину, по крайней мере, равную длине червяка, деленной на π. |
| 4. | Решение Джона Э. Ветцеля. [1] |
Задача Мозера о червяке (также известная как задача одеяла матери-червяка ) — нерешённая задача в геометрии, сформулированная австрийско-канадским математиком Лео Мозером в 1966 году. Задача требует найти область наименьшей площади , которая может вместить каждую плоскую кривую длины 1. Здесь «вместить» означает, что кривую можно вращать и переносить , чтобы она вписывалась в область. В некоторых вариациях задачи область ограничена выпуклостью .
Примеры
Например, круглый диск радиусом 1/2 может вместить любую плоскую кривую длины 1, поместив среднюю точку кривой в центр диска. Другое возможное решение имеет форму ромба с углами при вершине 60° и 120° и с длинной диагональю единичной длины. [2] Однако это не оптимальные решения; известны другие формы, которые решают задачу с меньшими площадями.
Свойства раствора
Не совсем тривиально, что существует покрытие минимальной площади. Альтернативная возможность заключается в том, что существует некоторая минимальная площадь, к которой можно приблизиться, но которую невозможно достичь. Однако существует наименьшее выпуклое покрытие. Его существование следует из теоремы выбора Бляшке . [3]
Также нетривиально определить, образует ли заданная форма покрытие. Джерриетс и Пул (1974) предположили, что форма вмещает каждую кривую единичной длины тогда и только тогда, когда она вмещает каждую многоугольную цепь единичной длины с тремя сегментами, что является более легко проверяемым условием, но Панракса, Ветцель и Вичирамала (2007) показали, что никакая конечная граница числа сегментов в полицепи не будет достаточной для этого теста.
Известные границы
Проблема остается открытой, но в ряде статей исследователи сократили разрыв между известными нижними и верхними границами. В частности, Норвуд и Пул (2003) построили (невыпуклое) универсальное покрытие и показали, что минимальная форма имеет площадь не более 0,260437; Герриетс и Пул (1974) и Норвуд, Пул и Лайдакер (1992) дали более слабые верхние границы. В выпуклом случае Ван (2006) улучшил верхнюю границу до 0,270911861. Кхандхавит, Пагонакис и Шрисвасди (2013) использовали стратегию минимума-максимума для площади выпуклого множества, содержащего сегмент, треугольник и прямоугольник, чтобы показать нижнюю границу 0,232239 для выпуклого покрытия.
В 1970-х годах Джон Ветцель предположил, что круговой сектор радиусом 30° с единичным радиусом является покрытием с площадью . Два доказательства этой гипотезы были независимо представлены Мовшовичем и Ветцелем (2017) и Панраксой и Вичирамалой (2021). Если это подтвердится, это снизит верхнюю границу для выпуклого покрытия примерно на 3%.
Смотрите также
- Задача о перемещении дивана , задача нахождения формы максимальной площади, которую можно вращать и перемещать через L-образный коридор.
- Набор Какейя , набор минимальной площади, который может вместить любой отрезок линии единичной длины (с допустимыми перемещениями, но не поворотами)
- Задача Лебега об универсальном покрытии : найти наименьшую выпуклую область, которая может покрыть любое плоское множество единичного диаметра.
- Задача Беллмана о заблудившихся в лесу : найти кратчайший путь к выходу из леса известных размеров и формы.
Примечания
- ^ http://researchgate.net/figure/The-smallest-known-worm-cover_fig3_268673536
- ^ Джерриетс и Пул (1974).
- ^ Норвуд, Пул и Лайдакер (1992) приписывают это наблюдение неопубликованной рукописи Лайдакера и Пула, датированной 1986 годом.
Ссылки
- Джерриетс, Джон; Пул, Джордж (1974), «Выпуклые области, покрывающие дуги постоянной длины», The American Mathematical Monthly , 81 (1): 36–41, doi :10.2307/2318909, JSTOR 2318909, MR 0333991.
- Khandhawit, Tirasan; Pagonakis, Dimitrios; Sriswasdi, Sira (2013), "Нижняя граница для задач о выпуклой оболочке и универсальном покрытии", International Journal of Computational Geometry & Applications , 23 (3): 197–212, arXiv : 1101.5638 , doi : 10.1142/S0218195913500076, MR 3158583, S2CID 207132316.
- Норвуд, Рик; Пул, Джордж (2003), «Улучшенная верхняя граница для задачи о червях Лео Мозера», Дискретная и вычислительная геометрия , 29 (3): 409–417, doi : 10.1007/s00454-002-0774-3 , MR 1961007.
- Норвуд, Рик; Пул, Джордж; Лайдакер, Майкл (1992), «Проблема червяка Лео Мозера», Дискретная и вычислительная геометрия , 7 (2): 153–162, doi : 10.1007/BF02187832 , MR 1139077.
- Panraksa, Chatchawan; Wetzel, John E.; Wichiramala, Wacharin (2007), "Покрытие n -сегментных единичных дуг недостаточно", Discrete and Computational Geometry , 37 (2): 297–299, doi : 10.1007/s00454-006-1258-7 , MR 2295060.
- Ван, Вэй (2006), «Улучшенная верхняя граница для задачи о червях», Acta Mathematica Sinica , 49 (4): 835–846, MR 2264090.
- Панракса, Чатчаван; Вичирамала, Вачарин (2021), «Сектор Ветцеля покрывает единичные дуги» , Periodica Mathematica Hungarica , 82 (2): 213–222, arXiv : 1907.07351 , doi : 10.1007/s10998-020-00354-x, S2CID 225397486.
- Мовшович, Евгения; Ветцель, Джон (2017), «Единичные дуги, подходящие для укладки в единичный сектор 30°» , Advances in Geometry , 17 (4): 497–506, doi :10.1515/advgeom-2017-0011, S2CID 125746596.
