Matrix (mathematics)

Example of the problem resolution.

In mathematics, the mountain climbing problem is a problem of finding the conditions that two function forming profiles of a two-dimensional mountain must satisfy, so that two climbers can start on the bottom on the opposite sides of the mountain and coordinate their movements to reach to the top while always staying at the same height. This problem was named and posed in this form by James V. Whittaker in 1966, but its history goes back to Tatsuo Homma, who solved a version of it in 1952. The problem has been repeatedly rediscovered and solved independently in different context by a number of people (see the references).

In the past two decades the problem was shown to be connected to the weak Fréchet distance of curves in the plane (see Buchin et al.), various planar motion planning problems in computational geometry (see Goodman et al.), the square peg problem (see Pak), semigroup of polynomials (see Baird and Magill), etc. The problem was popularized in the article by Goodman et al., which received the MAA writing award in 1990.

Understanding the problem

It is easy to coordinate the climbers' movement between the peaks and valleys (local maxima and minima of the functions). The difficulty is that to progress, the climbers must occasionally go down the mountain, either one or the other, or both climbers. Similarly, either one or the other climber must backtrack towards the beginning of the journey. In fact, it has been observed that for a mountain with n peaks and valleys the number of turns can be as large as quadratic in n (see Buchin et al.). These difficulties make the problem unintuitive and sometimes rather difficult, both in theory and in practice.

Formulation

The following result is due to Huneke:

Suppose $f$ and $g$ are continuous functions from $[0,1]$ to $[0,1]$ with $f(0)=g(0)=0$ and $f(1)=g(1)=1$, and such that neither function is constant on an interval. Then there exist continuous functions $s$ and $t$ from $[0,1]$ to $[0,1]$ with $s(0)=t(0)=0$, $s(1)=t(1)=1$, and such that $f\circ s\,=\,g\circ t$, where "$\circ$" stands for a composition of functions.

To see heuristically that the result does not extend to all continuous functions, note that if $f$ has a constant interval while $g$ has a highly oscillating interval on the same level, then the first climber would be forced to go back and forth infinitely many times, and thus can never reach the top.

It is also known that for the piecewise linear functions there are no obstructions, i.e. the climbers can always coordinate their movements to get to the top (see Whittaker).

Proof in the piecewise linear case

Consider a graph $G$ of all positions on a mountain both climbers can occupy on the same level. This graph is piecewise linear, i.e. a union of intervals, and can be viewed as a graph in Graph theory. Note that $G$ may or may not be connected. The vertices of the intervals correspond to peaks and valleys of the functions. There are three cases:

1. One climber is at a peak or a valley, another climber is in between two of them,

2. Both climbers are at a peak or at valley.

3. One climber is at a peak and one is at valley.

In the first case such vertex of $G$ has two adjacent intervals, in the second case it has four, and in the last case zero. Therefore, graph $G$ has all vertices of even degree, except for the point $(0,0)$ corresponding to two climbers on the bottom and the point $(1,1)$ corresponding to two climbers on top of the mountain. Applying the handshaking lemma to the connected component of $G$ containing $(0,0)$ we conclude that $(0,0)$ and $(1,1)$ are in the same connected component of $G$. This implies that there is a path from $(0,0)$ to $(1,1)$ in $G$. In the language of mountain climbers, this gives a way to coordinate the climbers' movement to reach the top of the mountain.

References

• Tatsuo Homma, A theorem on continuous functions, Kōdai Math. Semin. Rep. 1952, 13–16.
• R. Sikorski, K. Zarankiewicz, On uniformization of functions. I. Fundam. Math. 41 (1955), 339–344.
• J.S. Lipiński, Sur l'uniformisation des fonctions continues, Bull. Acad. Pol. Sci. Cl. III 5 (1957), 1019–1021.
• Jerzy Mioduszewski, On a quasi-ordering in the class of continuous mappings of closed interval into itself, Colloq. Math. 9 (1962), 233–240.
• James V. Whittaker, A mountain-climbing problem, Canad. J. Math. 18 (1966), 873–882.
• John P. Huneke, Mountain climbing, Trans. Amer. Math. Soc. 139 (1969), 383–391.
• M. A. McKiernan, Mountain climbing: an alternate proof, Aequationes Math. 28 (1985), no. 1–2, 132–134.
• Jacob E. Goodman, János Pach, Chee-K. Yap, Mountain climbing, ladder moving, and the ring-width of a polygon, Amer. Math. Monthly 96 (1989), no. 6, 494–510.
• Tamás Keleti, The mountain climbers' problem, Proc. Amer. Math. Soc. 117 (1993), no. 1, 89–97.
• B.B. Baird, K.D. Magill, Jr., Green's R, D and H relations for generalized polynomials, Semigroup Forum 55 (1997), no. 3, 267–293.
• Víctor Jiménez López, An elementary solution to the mountain climbers' problem, Aequationes Math. 57 (1999), no. 1, 45–49.
• Igor Pak, Lectures on Discrete and Polyhedral Geometry, Section 5.
• Kevin Buchin, Maike Buchin, Christian Knauer, Günter Rote, and Carola Wenk, How difficult is it to walk the dog?, in Proc. 23rd European Workshop on Computational Geometry (Graz, 2007), pp. 170–173.

External links

• The Parallel Mountain Climbers Problem, a description and a Java applet solution.
• MAA Writing Award