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 difficulties 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] 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.

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:

According to the handshaking lemma, every connected component of an undirected graph has an odd 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

References

External links

This article is issued from Wikipedia - version of the Sunday, December 20, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.