爬山问题

一个显然的例子。

爬山问题（英语：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.