Проблема альпинизма - 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}$ . На языке альпинистов это дает возможность координировать движение альпинистов, чтобы достичь вершины горы.

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

Примечания

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

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

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

[FOOTNOTEBuchinBuchinKnauerRote2007-1] а ^б Бучин и др. (2007).

[FOOTNOTEGoodmanPachYap1989-2] Гудман, Пач и Яп (1989).

[FOOTNOTEPak2010-3] Пак (2010).

[FOOTNOTEBairdMagill1997-4] Бэрд и Мэджилл (1997).

[5] "Восхождение на гору, перемещение лестницы и ширина кольца многоугольника", Письменные награды, Математическая ассоциация Америки, 1990, получено 2015-12-19.

[FOOTNOTEWhittaker1966-6] Уиттакер (1966).

[1]

[2]

[3]

[4]

[5]

[6]