Mountain climbing problem

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 (1966), but its history goes back to Tatsuo Homma (1952), who solved a version of it. 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,^[1] various planar motion planning problems in computational geometry,^[2] the inscribed square problem,^[3] semigroup of polynomials,^[4] etc. The problem was popularized in the article by Goodman, Pach & Yap (1989), which received the Mathematical Association of America's Lester R. Ford Award in 1990.^[5]

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$ .^[1] These complications make the problem unintuitive and sometimes rather difficult, both in theory and in practice.

Formulation

The following result is due to Huneke (1969):

Suppose

f

and

g

are continuous functions from

[0,1]

[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]

[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.

On the other hand, it is not possible to extend this result to all continuous function. For, if $f$ has constant height over an interval while $g$ has infinitely many oscillations that pass through the same height, then the first climber may be forced to go back and forth infinitely many times, and thus can never reach the top.

For the piecewise linear functions there are no obstructions. In this case, the climbers can always coordinate their movements to get to the top, regardless of whether there are intervals of constant height.^[6]

Proof in the piecewise linear case

Suppose that both functions are piecewise linear, and do not have any intervals of constant height.

Consider the set of all pairs $(x,y)$ for which a first climber at $x$ and a second climber at $y$ would have the same height as each other. If we interpret these pairs as the Cartesian coordinates of points in the plane, then this set is a union of line segments. It can be interpreted as the drawing of an undirected graph $G$ that has a vertex at each line segment endpoint or crossing, and an edge for each portion of a line segment that connects two vertices.

This graph may or may not be connected. It has vertices of the following types:

At the vertex $(0,0)$ the degree of the vertex (the number of incident edges) is one: the only possible direction for both climbers to go is onto the mountain. Similarly, at $(1,1)$ the degree is one, because both climbers can only return back down the mountain.
At a vertex where neither climber is at a peak or a valley, then the degree is two: it is only possible for both climbers to go up, or both to go down.
At a vertex where one climber is at a peak or a valley and the other one is not, then the degree is again two: the climber at the peak or valley has two choices of which way to go, and the other climber can only go one way.
At a vertex where both clmbers are at peaks or both climbers are at valleys, the degree is four: both climbers may choose independently of each other which direction to go.
The set of pairs $(x,y)$ used to define the graph $G$ may also include points where one climber is at a peak and the other is at a valley. These points may be interpreted as isolated vertices of $G$ : neither climber can move, so the degree is zero.

According to the handshaking lemma, every connected component of an undirected graph has an even number of odd-degree vertices. Since the only odd-degree vertices are $(0,0)$ and $(1,1)$ , these two vertices must belong to the same connected component. That is, there must be 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.

The proof for functions that are piecewise linear but that allow intervals of constant height is similar, but involves a more complicated case analysis. Alternatively, one can find a path for modified functions in which all the intervals of constant height have been collapsed to points, and then extend the resulting path to the original functions.

Notes

1 2 Buchin et al. (2007).
↑ Goodman, Pach & Yap (1989).
↑ Pak (2010).
↑ Baird & Magill (1997).
↑ "Mountain Climbing, Ladder Moving, and the Ring-Width of a Polygon", Writing Awards, Mathematical Association of America, 1990, retrieved 2015-12-19 .
↑ Whittaker (1966).

References

Baird, B. B.; Magill, K. D., Jr. (1997), "Green's ${\mathcal {R}}$ , ${\mathcal {D}}$ and ${\mathcal {H}}$ relations for generalized polynomials", Semigroup Forum, 55 (3): 267–293, doi:10.1007/PL00005929, MR 1469444 .
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, MR 999412 .
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, 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 .
Keleti, Tamás (1993), "The mountain climbers' problem", Proceedings of the American Mathematical Society, 117 (1): 89–97, doi:10.2307/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 781218 .
Mioduszewski, J. (1962), "On a quasi-ordering in the class of continuous mappings of a closed interval into itself", Colloquium Mathematicum, 9: 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: 339–344, MR 0072465 .
Tucker, Alan (1995), "The parallel climbers puzzle" (PDF), Math Horizons, 3 (2): 22–24 .
Whittaker, James V. (1966), "A mountain-climbing problem", Canadian Journal of Mathematics, 18: 873–882, doi:10.4153/CJM-1966-087-x, MR 0196013 ..

External links

The Parallel Mountain Climbers Problem, a description and a Java applet solution.

This article is issued from Wikipedia - version of the 11/23/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.