Mountain climbing problem


In mathematics, the mountain climbing problem is a problem of finding the conditions that two functions 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 meet while always staying at the same height. This problem was named and posed in this form by, but its history goes back to, who solved a version of it. The problem has been repeatedly rediscovered and solved independently in different context by a number of people.
In the past two decades the problem was shown to be connected to the weak Fréchet distance of curves in the plane, various planar motion planning problems in computational geometry, the inscribed square problem, semigroup of polynomials, etc. The problem was popularized in the article by, which received the Mathematical Association of America's Lester R. Ford Award in 1990.

Understanding the problem

It is easy to coordinate the climbers' movement between the peaks and valleys. 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 peaks and valleys the number of turns can be as large as quadratic in. These complications make the problem unintuitive and sometimes rather difficult, both in theory and in practice.

Formulation

The following result is due to :
On the other hand, it is not possible to extend this result to all continuous functions. For, if has constant height over an interval while 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.

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 for which a first climber at and a second climber at 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 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:
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 and, these two vertices must belong to the same connected component. That is, there must be a path from to in. 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.