Проблема альпинизма - Mountain climbing problem

Пример решения проблемы

В математика, то проблема альпинизма проблема нахождения условий, при которых два функции формирование профилей из двумерный гора должны удовлетворить, так что два альпинисты могут начинать с противоположных сторон горы и координировать свои движения для встречи (возможно, наверху), всегда оставаясь на одной и той же высоте. Эта проблема была названа и поставлена ​​в такой форме Джеймсом В. Уиттакером (1966 ), но его история восходит к Тацуо Хомме (1952 ), который решил одну из версий. Проблема неоднократно открывалась заново и решалась независимо в различном контексте рядом людей (см. Ссылки ниже).

В последние два десятилетия было показано, что проблема связана со слабыми Расстояние Фреше из кривые в плоскости,^[1] различные планарные планирование движения проблемы в вычислительная геометрия,^[2] то вписанная квадратная задача,^[3] полугруппа из многочлены,^[4] и др. Проблема была популяризирована в статье Гудман, Пач и Яп (1989), получивший Математическая ассоциация Америки Премия Лестера Р. Форда в 1990 году.^[5]

Понимание проблемы

Легко скоординировать передвижение альпинистов между пиками и впадинами (локальные максимумы и минимумы функций). Сложность в том, что для прогресса альпинисты должны время от времени спускаться с горы, один или другой, или оба альпиниста. Точно так же один или другой альпинист должен вернуться к началу пути. Фактически, было замечено, что для горы с п пиков и провалов количество витков может достигать квадратичный в п.^[1] Эти сложности делают задачу неинтуитивной, а иногда и довольно сложной как в теории, так и на практике.

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

Следующий результат обусловлен Хунеке (1969):

Предполагать ${displaystyle f}$ и ${displaystyle g}$ находятся непрерывные функции из ${displaystyle [0,1]}$ к ${displaystyle [0,1]}$ с ${displaystyle f(0)=g(0)=0}$ и ${displaystyle f(1)=g(1)=1}$, и такой, что ни одна функция не постоянный на интервал. Тогда существуют непрерывные функции ${displaystyle s}$ и ${displaystyle t}$ из ${displaystyle [0,1]}$ к ${displaystyle [0,1]}$ с ${displaystyle s(0)=t(0)=0}$, ${displaystyle s(1)=t(1)=1}$, и такой, что ${displaystyle fcirc s,=,gcirc t}$, куда "${displaystyle circ }$"означает состав функций.

С другой стороны, распространить этот результат на все непрерывные функции невозможно. Ведь если ${displaystyle f}$ имеет постоянную высоту в течение определенного интервала, в то время как ${displaystyle g}$ имеет бесконечно много колебаний, которые проходят через одну и ту же высоту, тогда первый альпинист может быть вынужден идти вперед и назад бесконечно много раз и, таким образом, никогда не сможет достичь вершины.

Для кусочно-линейные функции нет никаких препятствий. В этом случае альпинисты всегда могут координировать свои движения, чтобы добраться до вершины, независимо от того, есть ли интервалы постоянной высоты.^[6]

Доказательство в кусочно-линейном случае.

Предположим, что обе функции кусочно-линейны и не имеют интервалов постоянной высоты.

Рассмотрим множество всех пар ${displaystyle (x,y)}$ для которого первый альпинист на ${displaystyle x}$ и второй альпинист на ${displaystyle y}$ будут иметь одинаковую высоту. Если мы интерпретируем эти пары как Декартовы координаты точек на плоскости, то это множество является объединением отрезки линии. Его можно интерпретировать как Рисование из неориентированный граф ${displaystyle G}$ который имеет вершину в каждой конечной точке или пересечении линейного сегмента и ребро для каждой части линейного сегмента, соединяющей две вершины.

Этот график может быть или не быть связаны. Имеет вершины следующих типов:

• В вершине ${displaystyle (0,0)}$ то степень вершины (количество инцидентных ребер) равно единице: единственное возможное направление для обоих альпинистов - на гору. Аналогично в ${displaystyle (1,1)}$ степень равна единице, потому что оба альпиниста могут вернуться только с горы.
• В вершине, где ни один альпинист не находится на вершине или в долине, тогда степень равна двум: только оба альпиниста могут подняться вверх или оба могут спуститься вниз.
• В вершине, где один альпинист находится на вершине или в долине, а другой нет, тогда степень снова равна двум: у альпиниста на вершине или в долине есть два выбора, по какому пути идти, а другой альпинист может только идти. в одну сторону.
• В вершине, где оба альпиниста находятся на пиках или оба альпиниста находятся в долинах, степень равна четырем: оба альпиниста могут независимо друг от друга выбирать, в каком направлении идти.
• Набор пар ${displaystyle (x,y)}$ используется для определения графика ${displaystyle G}$ может также включать точки, где один альпинист находится на вершине, а другой - в долине. Эти точки можно интерпретировать как изолированные вершины ${displaystyle G}$: ни один альпинист не может двигаться, поэтому градус равен нулю.

Согласно лемма о рукопожатии, каждая связная компонента неориентированного графа имеет четное число вершин нечетной степени, так как вершины нечетной степени ${displaystyle (0,0)}$ и ${displaystyle (1,1)}$, эти две вершины должны принадлежать одной компоненте связности. То есть должен быть дорожка из ${displaystyle (0,0)}$ к ${displaystyle (1,1)}$ в ${displaystyle G}$. На языке альпинистов это дает возможность координировать движение альпинистов, чтобы достичь вершины горы.

Доказательство для кусочно-линейных функций, допускающих интервалы постоянной высоты, аналогично, но требует более сложного анализа случая. В качестве альтернативы можно найти путь для модифицированных функций, в котором все интервалы постоянной высоты свернуты до точек, а затем расширить полученный путь до исходных функций.

Примечания

1. Бучин и др. (2007).
2. Гудман, Пач и Яп (1989).
3. Пак (2010).
4. Бэрд и Мэджилл (1997).
5. "Восхождение на гору, перемещение лестницы и ширина кольца многоугольника", Письменные награды, Математическая ассоциация Америки, 1990, получено 2015-12-19.
6. Уиттакер (1966).

Рекомендации

• Baird, B. B .; Мэджилл, К. Д., младший (1997), "Грин" ${displaystyle {mathcal {R}}}$, ${displaystyle {mathcal {D}}}$ и ${displaystyle {mathcal {H}}}$ соотношения для обобщенных многочленов », Полугруппа Форум, 55 (3): 267–293, Дои:10.1007 / PL00005929, МИСТЕР  1469444.
• Бучин, Кевин; Бучин, Майке; Кнауэр, Кристиан; Роте, Гюнтер; Венк, Карола (2007), "Насколько сложно выгуливать собаку?", Proc. 23-й Европейский семинар по вычислительной геометрии (Грац, 2007 г.), стр. 170–173.
• Гудман, Джейкоб Э.; Пах, Янош; Yap, Chee-K. (1989), «Альпинизм, перемещение по лестнице и ширина кольца многоугольника» (PDF), Американский математический ежемесячный журнал, 96 (6): 494–510, Дои:10.2307/2323971, JSTOR  2323971, МИСТЕР  0999412.
• Хомма, Тацуо (1952), "Теорема о непрерывных функциях", Отчеты математического семинара Кодаи, 4: 13–16, Дои:10,2996 / kmj / 1138843207, МИСТЕР  0049988.
• Хунеке, Джон Филип (1969), «Альпинизм», Труды Американского математического общества, 139: 383–391, Дои:10.2307/1995331, JSTOR  1995331, МИСТЕР  0239013.
• Хименес Лопес, Виктор (1999), «Элементарное решение проблемы альпинистов», Aequationes Mathematicae, 57 (1): 45–49, Дои:10.1007 / с000100050069, МИСТЕР  1675749.
• Келети, Тамаш (1993), "Проблема альпинистов", Труды Американского математического общества, 117 (1): 89–97, Дои:10.2307/2159702, JSTOR  2159702, МИСТЕР  1123655.
• Липинский, Дж. С. (1957), "Sur l'uniformisation des fonctions продолжается", Бык. Акад. Полон. Sci. Cl. III, 5: 1019–1021, LXXXV, МИСТЕР  0095224.
• Маккирнан, М.А. (1985), "Альпинизм: альтернативное доказательство", Aequationes Mathematicae, 28 (1–2): 132–134, Дои:10.1007 / BF02189402, МИСТЕР  0781218.
• Миодушевский Дж. (1962), "О квазиупорядочении в классе непрерывных отображений отрезка в себя", Математический коллоквиум, 9 (2): 233–240, Дои:10.4064 / см-9-2-233-240, МИСТЕР  0143181.
• Пак, Игорь (2010), Лекции по дискретной и многогранной геометрии, п. 39.
• Sikorski, R .; Заранкевич, К. (1955), «Об униформизации функций. I», Fundamenta Mathematicae, 41 (2): 339–344, Дои:10.4064 / fm-41-2-339-344, МИСТЕР  0072465.
• Такер, Алан (1995), «Загадка параллельных альпинистов» (PDF), Математические горизонты, 3 (2): 22–24, Дои:10.1080/10724117.1995.11974954.
• Уиттакер, Джеймс В. (1966), "Проблема альпинизма", Канадский математический журнал, 18: 873–882, Дои:10.4153 / CJM-1966-087-x, МИСТЕР  0196013..

внешняя ссылка

• Задача параллельных альпинистов, описание и Java-апплет решение.