爬山問題

一個顯然的例子。

爬山問題（英語：mountain climbing problem）是一個數學問題，设想一個二維山脈（表示為一個連續函數），並詢問兩個登山者是否能做到：兩個人從山脈的左右兩側海平面開始，並在任何時候都保持相同的高度，最終在山頂會合。研究表明，當山脈只有有限數量的山峰和山谷時，都可以如此協調登山者的移動；但若山脈有無限數量的山峰和山谷就不一定成立。

此問題由 James V. Whittaker 在 1966 年以此形式命名並提出，但其歷史可以追溯到本間龍雄（Tatsuo Homma），他在 1952 年解決了一個相關版本。之後這個問題也在不同背景下被許多人反覆獨立地重新發現和解決（詳見下面的資料來源）。

自 1990 年代以來，該問題被證明與平面曲線的弱 Fréchet 距離、計算幾何中的各種平面運動規劃問題、內接正方形問題、多項式半群等相關聯。此問題因 Goodman, Pach & Yap (1989) 的文章而廣受歡迎，該文章於 1990 年榮獲美國數學協會的 Lester R. Ford 獎。

分析

此問題可以重新闡述為：給定一對連續函數 $f,g$ （分別對應於山脈左右兩側經過縮放的形狀），其中:

• $f(0)=g(0)=0$ 且
• $f(1)=g(1)=1$ 且
• 對於所有 $x\in [0,1]$, $f(x),g(x)\in [0,1]$

是否能找到另一對函數 $x_{1},x_{2}$ （代表登山者在時間 $t$ 時的水平位置）滿足:

• $x_{1}(0)=x_{2}(0)=0$ 且
• $x_{1}(1)=x_{2}(1)=1$

使得合成函數 $f\circ x_{1}$ 與 $g\circ x_{2}$ （代表登山者在時間 $t$ 時的海拔高度）相同？

有限數量的山峰和山谷

這是爬山問題中需要回溯的一個範例。原始圖片是動畫 SVG，點擊即可觀看。

當函數 $f,g$ 只有有限數量的山峰和山谷（即局部極大值與局部最小值）時，總是能夠協調登山者們的移動。 這可以用一種競賽樹來證明：一個無向圖 $G$ ，當 $f(x_{1})=g(x_{2})$ ，且 $f(x_{1})$ 或 $g(x_{2})$是局部最大值或最小值，頂點標記為 $(x_{1},x_{2})$。兩個頂點之間會有一條邊相連若且唯若其中一個節點可以直接從另一個節點到達；只有當登山者在該位置有非顯然的選擇時，頂點的度數才會大於一。

• 在頂點 $(0,0)$ 處，其度數為一：因為兩位登山者唯一能走的方向就是往山上移動。同樣地，在 $(1,1)$ 處，度數也是一，因為兩位登山者只能往山下回程。
• 當一個登山者位於山峰或山谷而另一個不在時，此頂點的度數為二：位於山峰或山谷的登山者有兩種方向可選擇，而另一位登山者只能選擇一個方向。
• 若兩位登山者都位於山峰或都位於山谷，此頂點的度數為四：意味著兩位登山者可以各自獨立選擇前進方向。
• 若一位登山者位於山峰而另一位在山谷，此頂點的度數為零：這種情況是不可能的。（換句話說，若存在這樣的頂點，則圖 $G$ 就不是連通的。）

根據握手引理（Handshaking lemma），任何無向圖的每個連通元件都必須包含偶數個度數為奇數的頂點。在我們討論的圖 $G$ 中，唯一的奇數度數頂點是 $(0,0)$ 和 $(1,1)$。這表示這兩個頂點必須屬於同一個連通元件。也就是說，圖 $G$ 中一定存在一條從 $(0,0)$ 到 $(1,1)$ 的路徑，這條路徑就說明了如何協調登山者的移動以到達山頂。

值得注意的是，對於一個有 $n$ 個山峰和山谷的山脈，這條路徑的長度（大致對應於其中一個或兩個登山者需要「回溯（backtrack）」的次數）可以達到 $n$ 的平方量級。

然而，當函數 $f,g$ 具有無限數量的局部極值時，這個技巧就失效了。在這種情況下，$G$ 不會是一個有限圖，因此握手引理不再適用。儘管 $(0,0)$ 和 $(1,1)$ 可能仍然是連通的，但它們之間的路徑可能包含無限數量的頂點，這可能導致登山者需要「無限長的時間」才能走完。

無限數量的山峰與山谷

以下是 Huneke (1969) 提出的結果：

假設 $f$ 和 $g$ 為從 $[0,1]$ 到 $[0,1]$ 的連續函數，且 $f(0)=g(0)=0$ 與 $f(1)=g(1)=1$，同時這兩個函數在任何區間上都不是常數函數。那麼，存在從 $[0,1]$ 到 $[0,1]$ 的連續函數 $s$ 和 $t$ 且 $s(0)=t(0)=0$, $s(1)=t(1)=1$, 使得 $f\circ s\,=\,g\circ t$（其中 "$\circ$" 表示函數的複合）。

另一方面，此結果並不能推廣到所有連續函數。這是因為如果 $f$ 在某個區間上保持固定高度，而 $g$ 在相同高度上發生了無限多次震盪，那麼第一位登山者可能被迫在該區間上無限次地來回移動，導致他/她到達山頂的路徑變得無限長。James V. Whittaker （1966） 提供了一個具體的例子，其中涉及函數 $x\sin(x^{-1})$。

參考文獻

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

外部連結

• The Parallel Mountain Climbers Problem, a description and a Java applet solution.
• [1] （页面存档备份，存于互联网档案馆） another visualization of the set of solutions, as a webapp.