Mountain climbing problem
In mathematics, the mountain climbing problem is a mathematical problem that considers a two-dimensional mountain range (represented as a continuous function), and asks whether it is possible for two mountain climbers starting at sea level on the left and right sides of the mountain to meet at the summit, while maintaining equal altitudes at all times.
It has been shown that when the mountain range has only a finite number of peaks and valleys, it is always possible to coordinate the climbers' movements, but this does not necessarily hold when it has an infinite number of peaks and valleys.
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 contexts by a number of people (see references below).
Since the 1990s, 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] The problem can be rephrased as asking whether, for a given pair of continuous functions
(corresponding to rescaled versions of the left and right faces of the mountain) where: Is it possible to find another pair of functions
(representing the climbers' horizontal positions at time
(which represent the climbers' altitudes at time
have only a finite number of peaks and valleys (local maxima and local minima) it is always possible to coordinate the climbers' movements.
[6] This can be shown by drawing out a sort of game tree: an undirected graph
Two vertices will be connected by an edge if and only if one node is immediately reachable from the other; the degree of a vertex will be greater than one only when the climbers have a non-trivial choice to make from that position.
According to the handshaking lemma, every connected component of an undirected graph has an even number of odd-degree vertices.
, these two vertices must belong to the same connected component.
That path tells how to coordinate the climbers' movement to the summit.
It has been observed that for a mountain with n peaks and valleys the length of this path (roughly corresponding to the number of times one or the other climber must "backtrack") can be as large as quadratic in n.[1] This technique breaks down when
have an infinite number of local extrema.
would not be a finite graph, so the handshaking lemma would not apply:
might be connected but only by a path with an infinite number of vertices, possibly taking the climbers "infinite time" to traverse.
The following result is due to Huneke (1969): On the other hand, it is not possible to extend this result to all continuous functions.
has constant height over an interval while
has infinitely many oscillations passing through the same height, then the first climber may be forced to go back and forth over that interval infinitely many times, making his path to the summit infinitely long.
[6] James V. Whittaker (1966) gives a concrete example involving
