登山問題

数学において、登山問題（さんさんじゅうじけん、英: mountain mountain mountain ）は、2次元の山脈（連続関数として表現される）を考慮し、山の左右両側の海抜ゼロメートル地点からスタートした2人の登山者が、常に等しい高度を保ちながら山頂で出会うことができるかどうかを問う数学の問題である。この問題は、ジェームズ・V・ウィテカー（1966年）によってこの形で命名され提起されたが、その歴史は、この問題の一種を解いた本間達雄（1952年）に遡る。この問題は、異なる文脈で多くの人々によって繰り返し再発見され、独立に解かれてきた（下記の参考文献を参照）。

1990年代以降、この問題は平面曲線の弱いフレシェ距離、 ^[1]計算幾何学におけるさまざまな平面運動計画問題、^[2]内接正方形問題、^[3]多項式の半群、^[4]などと関連していることが示されました。この問題は、Goodman、Pach、Yap (1989) による論文で広く知られるようになり、 1990年に米国数学会のレスター・R・フォード賞を受賞しました。 ^[5]

この問題は、（山の左側面と右側面の再スケール版に対応）を持つ連続関数の与えられたペアに対して、関数合成と（時刻 における登山者の水平位置）が同じ関数となるような別の関数のペアを見つけることができるかどうかを尋ねるものとして言い換えることができます。 ${\displaystyle f,g}$${\displaystyle f(0)=g(0)=0,f(1)=g(1)=1}$${\displaystyle x_{1},x_{2}}$${\displaystyle x_{1}(0)=x_{2}(0)=0,x_{1}(1)=x_{2}(1)=1}$${\displaystyle t}$ ${\displaystyle f\circ x_{1}}$${\displaystyle g\circ x_{2}}$${\displaystyle t}$

山と谷（極大値と極小値）の数が有限であれば、登山者の動きを調整することが常に可能です。^[6]これは、一種のゲームツリーを描くことで示せます。これは、 またはが極大値または極小値であるときは常に というラベルの付いた頂点を持つ無向グラフです。2つの頂点は、一方のノードが他方のノードから直接到達可能な場合にのみ、辺で接続されます。頂点の次数は、登山者がその位置から行う重要な選択がある場合にのみ、1より大きくなります。 ${\displaystyle f,g}$ ${\displaystyle G}$${\displaystyle (x_{1},x_{2})}$${\displaystyle f(x_{1})=g(x_{2})}$${\displaystyle f(x_{1})}$${\displaystyle g(x_{2})}$

• 頂点では、次数は 1 です。つまり、両方の登山者が進むことができる唯一の方向は山に登ることです。同様に、頂点では、両方の登山者が山を下りることしかできないため、次数は 1 です。${\displaystyle (0,0)}$${\displaystyle (1,1)}$
• 一方の登山者が山頂または谷にいて、もう一方がそうでない頂点では、次数は 2 です。つまり、山頂または谷にいる登山者はどちらの方向に進むか 2 つの選択肢があり、もう一方の登山者は 1 つの方向しか進むことができません。
• 両方の登山者が山頂にいる頂点、または両方の登山者が谷にいる頂点では、次数は 4 です。つまり、両方の登山者は互いに独立してどちらの方向に進むかを選択できます。
• 一方の登山者が頂上にあり、もう一方が谷にある頂点では、次数は 0 です。つまり、そのような位置は到達不可能です。(つまり、そのような頂点が存在する場合、グラフは接続されていません。)${\displaystyle G}$

ハンドシェイク補題によれば、無向グラフの連結成分には奇数次の頂点が偶数個あります。 全体で奇数次の頂点は と だけなので、これら2 つの頂点は同じ連結成分に属している必要があります。つまり、には からへのパスが含まれている必要があります。そのパスは、登山者の動きを山頂まで調整する方法を示します。 ${\displaystyle G}$${\displaystyle (0,0)}$${\displaystyle (1,1)}$${\displaystyle G}$${\displaystyle (0,0)}$${\displaystyle (1,1)}$

n 個の山頂と谷を持つ山の場合、この経路の長さ（どちらかの登山者が「後戻り」しなければならない回数にほぼ相当）はnの2 乗にまで達する可能性があることが観察されています。^[1]

この手法は、局所的極値が無限にある場合には機能しません。その場合、は有限グラフではないため、ハンドシェイク補題は適用されません。また、無限数の頂点を持つパスによってのみ接続される可能性があり、登山者が横断するには「無限の時間」がかかる可能性があります。 ${\displaystyle f,g}$${\displaystyle G}$${\displaystyle (0,0)}$${\displaystyle (1,1)}$

以下の結果はHuneke (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 f\circ s\,=\,g\circ t}$${\displaystyle \circ}$

一方、この結果をすべての連続関数に拡張することはできません。 が区間内で一定の高さを持ち、 が同じ高さを通過する振動が無限にある場合、最初の登山者はその区間を無限回往復しなければならず、頂上までの道のりが無限に長くなる可能性があります。^[6] James V. Whittaker (1966) は に関する具体的な例を示しています。^[6]${\displaystyle f}$${\displaystyle g}$${\displaystyle x\sin(x^{-1})}$

• Baird, BB; Magill, KD Jr. (1997)、「グリーンの、および一般化多項式の関係」、Semigroup Forum、55 (3): 267–293、doi :10.1007/PL00005929、MR  1469444、S2CID  120449490${\displaystyle {\mathcal {R}}}$${\displaystyle {\mathcal {D}}}$${\displaystyle {\mathcal {H}}}$。
• ブチン、ケビン。マイケ・ブチン;クナウアー、クリスチャン。ローテ、ギュンター。ウェンク、カロラ(2007)、「犬の散歩はどのくらい難しいですか?」、Proc.第 23 回ヨーロッパ計算幾何ワークショップ (グラーツ、2007)、170–173 ページ。
• グッドマン、ジェイコブ E. ;パック、ヤノシュ; ヤップ、チー-K. (1989)、「山登り、はしご移動、および多角形のリング幅」(PDF)、アメリカ数学月刊誌、96 (6): 494–510、doi :10.2307/2323971、JSTOR  2323971、MR  0999412。
• 本間 辰雄 (1952)、「連続関数に関する定理」、 古代数学セミナー報告、4 :13–16、doi : 10.2996/kmj/1138843207、MR0049988。
• フネケ、ジョン・フィリップ（1969）、「登山」、アメリカ数学会誌、139：383-391、doi：10.2307/1995331、JSTOR  1995331、MR  0239013。
• Jiménez López、Víctor (1999)、「登山者の問題に対する基本的な解決策」、Aequationes Mathematicae、57 (1): 45–49、doi :10.1007/s000100050069、MR  1675749、S2CID  121912365。
• ケレティ、タマス (1993)、「登山家の問題」、アメリカ数学会紀要、117 (1): 89–97、doi :10.2307/2159702、JSTOR  2159702、MR  1123655。
• JS リピンスキ (1957)、「機能の統一化は続く」、Bull.アカド。ポロン。科学。 Cl. III、5 : 1019–1021、LXXXV、MR  0095224。
• マサチューセッツ州マッキーナン (1985)、「登山: 代替証明」、Aequationes Mathematicae、28 (1–2): 132–134、doi :10.1007/BF02189402、MR  0781218、S2CID  120938782。
• ミオドゥシェフスキ、J. (1962)、「閉区間のそれ自身への連続写像のクラスにおける準順序について」、コロキウム数学、9 (2): 233–240、doi : 10.4064/cm-9-2-233-240、MR  0143181。
• パク、イゴール（2010）、離散幾何学と多面体幾何学の講義、p. 39。
• シコルスキー、R.;ザランキエヴィッチ、K. (1955)、「関数の均一化について。I」、Fundamenta Mathematicae、41 (2): 339–344、doi : 10.4064/fm-41-2-339-344、MR  0072465。
• タッカー、アラン(1995)、「平行クライマーパズル」(PDF)、Math Horizo​​ns、3 (2): 22–24、doi :10.1080/10724117.1995.11974954。
• ウィテカー、ジェームズ V. (1966)、「山登り問題」、カナダ数学ジャーナル、18 : 873–882、doi : 10.4153/CJM-1966-087-x、MR  0196013、S2CID  124117059..

• 並列マウンテンクライマー問題の説明とJava アプレットのソリューション。