등산 문제

수학에서 등산문제는 2차원 산의 프로파일을 형성하는 두 가지 기능이 충족해야 하는 조건을 찾는 문제로서, 두 명의 등산객이 산 반대편 하단에서 출발하여 항상 같은 높이에 머물면서 만날 수 있도록(아마 정상에서) 움직임을 조율할 수 있다.이 문제는 제임스 5세에 의해 이 형태로 명명되고 제기되었다.휘태커(1966년) 그러나 그 역사는 한 버전을 해결한 옴마 다쓰오(1952년)에게 거슬러 올라간다.이 문제는 여러 사람에 의해 여러 맥락에서 독자적으로 재발견되고 해결되었다(아래 참조 참조).

1990년대 이후, 문제는 평면 내 곡선의 약한 프레셰트 거리,^[1] 계산 기하학에서의 다양한 평면 운동 계획 문제,^[2] 새겨진 사각형 문제,^[3] 다항식의 세미그룹 등과 ^[4]연관되어 있는 것으로 나타났다.이 문제는 미국수학협회 레스터 R을 받은 굿맨, 파치앤야프(1989)의 글에서 대중화됐다.1990년 포드상.^[5]

문제 이해

산봉우리와 계곡(기능의 국부적 최대치와 미니마) 사이에서 등산객들의 움직임을 쉽게 조율할 수 있다.어려운 점은 진척되기 위해서는 때때로 등산객들 중 한 명 또는 다른 한 명 또는 두 명 모두 산을 내려가야 한다는 것이다.마찬가지로, 한 명 또는 다른 한 명의 등반자는 여행의 시작을 향해 뒤로 물러나야 한다.실제로 산봉우리와 계곡이 n개인 산의 경우 턴 횟수가 n의 2차선만큼 클 수 있다는 것이 관찰되었다.^[1]이러한 복잡한 문제들은 문제를 비논리적이고 때로는 이론적으로나 실제적으로 다소 어렵게 만든다.

공식화

후네케(1969년)에 의한 결과는 다음과 같다.

Suppose ${\displaystyle f}$ and ${\displaystyle g}$ are continuous functions from ${\displaystyle [0,1]}$ to ${\displaystyle [0,1]}$ with ${\displaystyle f(0)=g(0)=0}$ and ${\displaystyle f(1)=g(1)=1}$, and such that neither function is constant틈틈이Then there exist continuous functions ${\displaystyle s}$ and ${\displaystyle t}$ from ${\displaystyle [0,1]}$ to ${\displaystyle [0,1]}$ with ${\displaystyle s(0)=t(0)=0}$, ${\displaystyle s(1)=t(1)=1}$, and such that ${\d$$isplaystyle f\\,=\,g\nft t$ 여기서 " ${\displaystyle }$ ${\displaystyle$\ \ $\}"$은 함수의 구성을 의미한다.

반면에, 이 결과를 모든 연속적인 기능에까지 확장하는 것은 불가능하다.왜냐하면, $f{\displaystyle }$ ${\displaystyle f}$이(가) 일정한 높이를 갖는$$ $반면{\displaystyle }$ g$${\$displaystyle g}$은 같은 높이를 통과하는 무한히 많은 진동을 가지고$$ 있다면, 첫 번째 등반자는 무한히 여러 번 왔다 갔다 해야 하므로, 따라서 결코 정상에 도달할 수 없다.

부분적인 선형 함수의 경우 장애물이 없다.이 경우 등반가들은 일정한 높이의 간격이 있는지 여부에 관계없이 항상 정상까지 오르기 위해 움직임을 조정할 수 있다.^[6]

조각과 같은 선형 케이스의 증거

두 함수 모두 조각처럼 선형이므로 일정한 높이의 구간이 없다고 가정하십시오.

$모든{\displaystyle }$ 쌍$({\displaystyle x}$, ${\displaystyle y}$){\$displaystyle$$(x$$,$$y$$)}$의 첫 번째 등반가와$$ 두 $번째{\displaystyle }$등반가가 서로 같은 키를 갖는$$ 쌍(x , y )을 고려하십시오.이러한 쌍을 평면에 있는 점의 데카르트 좌표로 해석하면 이 집합은 선 세그먼트의 조합이다.각 선 세그먼트 끝점 또는 교차점에 정점이 있는$$ 비방향 그래프 $G{\displaystyle }$ ${\displaystyle G}$와 두 정점을 연결하는 선 세그먼트의 각 부분에 대한 에지를 그린 것으로 해석할 수 있다.

이 그래프는 연결될 수도 있고 연결되지 않을 수도 있다.다음과 같은 유형의 정점을 가지고 있다.

• 꼭지점${\displaystyle }$(${\displaystyle 0}$,${\displaystyle 0}$ ) ${\displaystyle (0,0)}$에서 꼭지점 정도(사고 가장자리의 수)가 1이다: 두 등산객이 모두 산으로 갈 수 있는 유일한 방향이다.마찬가지로 (${\displaystyle 1,}$ $){\displaystyle (1,1)}$에서 학위는$$ 1이다. 두 등반가 모두 산을 내려올 수만 있기 때문이다.
• 어느 등산가도 산봉우리나 계곡에 있지 않은 꼭지점에서, 그 정도는 두 가지다: 두 등산가 모두 올라가거나 둘 다 내려갈 수위는 두 가지다.
• 한 명의 등반가가 산봉우리나 계곡에 있고 다른 한 명은 그렇지 않은 정점에서, 그 정도는 다시 두 가지다. 즉, 산봉우리나 계곡에 있는 등반가는 두 가지 길을 선택할 수 있고, 다른 등반가는 한 가지 길만 갈 수 있다.
• 두 등반가가 모두 정상에 있거나 두 등반가가 계곡에 있는 꼭지점에서, 두 등반가가 각각 어느 방향으로 갈지 선택할 수 있는 정도는 네 가지다.
• 그래프 $G{\displaystyle }$ ${\displaystyle G}$을(를) 정의하는 데 사용되는$$ 쌍$({\displaystyle x}$, y${\displaystyle }$) ${\displaystyle(x,y)}$에는 한 명의 등산객이 정상에 있고 다른 한 명은 계곡에 있는 지점도 포함될 수 있다$$.이러한 점들은 $G{\displaystyle }$ ${\displaystyle G}$의 고립된 정점으로 해석될 수 있다$.$ 두 등반가 모두 움직일 수 없으므로 도수는 0이다.

핸드셰이킹 보조기구에 따르면, 비방향 그래프의 연결된 모든 구성요소는 짝수 수의 홀수 정점을 가진다.홀수 도 정점만${\displaystyle }$(${\displaystyle 0}$, ${\displaystyle 0}$) ${\displaystyle (0,0)}$ 및${\displaystyle }$(${\displaystyle 1}$, 1)${\displaystyle (1,1)}$이므로$,$ 이 두 정점은 동일한 연결된 구성 요소에 속해야 한다.$즉{\displaystyle }$$,{\displaystyle }$ G ${\displaystyle G}$에 (${\displaystyle 0,}$ ${\displaystyle 0}$) ${\$$displaystyle ($$0,0)}$부터${\displaystyle }$($1)}$까지 길이 있어야 한다$.$ 산악인의 언어로는 등산객들의 산꼭대기까지의 움직임을 조정할 수 있는 방법을 제공한다.

부분적으로는 선형이지만 일정한 높이의 간격을 허용하는 함수에 대한 증거는 유사하지만 보다 복잡한 사례 분석을 수반한다.또는 일정 높이의 모든 구간이 포인트로 축소된 변형된 기능의 경로를 찾은 다음, 그 결과의 경로를 원래 기능으로 확장시킬 수 있다.

메모들

참조

• Baird, B. B.; Magill, K. D., Jr. (1997), "Green's ${\displaystyle {\mathcal {R}}}$, ${\displaystyle {\mathcal {D}}}$ and ${\displaystyle {\mathcal {H}}}$ relations for generalized polynomials", Semigroup Forum, 55 (3): 267–293, doi:10.1007/PL00005929, MR 1469444, S2CID 120449490.
• Buchin, Kevin; Buchin, Maike; Knauer, Christian; Rote, Günter; Wenk, Carola (2007), "How difficult is it to walk the dog?", Proc. 23rd European Workshop on Computational Geometry (Graz, 2007), pp. 170–173.
• Goodman, Jacob E.; Pach, János; Yap, Chee-K. (1989), "Mountain climbing, ladder moving, and the ring-width of a polygon" (PDF), American Mathematical Monthly, 96 (6): 494–510, doi:10.2307/2323971, JSTOR 2323971, MR 0999412.
• Homma, Tatsuo (1952), "A theorem on continuous functions", Kōdai Mathematical Seminar Reports, 4: 13–16, doi:10.2996/kmj/1138843207, MR 0049988.
• Huneke, John Philip (1969), "Mountain climbing", Transactions of the American Mathematical Society, 139: 383–391, doi:10.2307/1995331, JSTOR 1995331, MR 0239013.
• Jiménez López, Víctor (1999), "An elementary solution to the mountain climbers' problem", Aequationes Mathematicae, 57 (1): 45–49, doi:10.1007/s000100050069, MR 1675749, S2CID 121912365.
• Keleti, Tamás (1993), "The mountain climbers' problem", Proceedings of the American Mathematical Society, 117 (1): 89–97, doi:10.2307/2159702, JSTOR 2159702, MR 1123655.
• Lipiński, J. S. (1957), "Sur l'uniformisation des fonctions continues", Bull. Acad. Polon. Sci. Cl. III, 5: 1019–1021, LXXXV, MR 0095224.
• McKiernan, M. A. (1985), "Mountain climbing: an alternate proof", Aequationes Mathematicae, 28 (1–2): 132–134, doi:10.1007/BF02189402, MR 0781218, S2CID 120938782.
• Mioduszewski, J. (1962), "On a quasi-ordering in the class of continuous mappings of a closed interval into itself", Colloquium Mathematicum, 9 (2): 233–240, doi:10.4064/cm-9-2-233-240, MR 0143181.
• Pak, Igor (2010), Lectures on Discrete and Polyhedral Geometry, p. 39.
• Sikorski, R.; Zarankiewicz, K. (1955), "On uniformization of functions. I", Fundamenta Mathematicae, 41 (2): 339–344, doi:10.4064/fm-41-2-339-344, MR 0072465.
• Tucker, Alan (1995), "The parallel climbers puzzle" (PDF), Math Horizons, 3 (2): 22–24, doi:10.1080/10724117.1995.11974954.
• Whittaker, James V. (1966), "A mountain-climbing problem", Canadian Journal of Mathematics, 18: 873–882, doi:10.4153/CJM-1966-087-x, MR 0196013..

외부 링크

• 병렬 산악인 문제, 설명 및 Java 애플릿 솔루션.