↑ arvau

Wikipedia / 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 , but its history goes back to , 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, 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.

Analysis

(corresponding to rescaled versions of the left and right faces of the mountain) where:

  • ,

  • , and

) satisfying:

  • , and

) are identical?

Finite number of peaks and valleys

have only a finite number of peaks and valleys (local maxima and local minima) it is always possible to coordinate the climbers' movements. This can be shown by drawing out a sort of game tree: an undirected graph is a local maximum or minimum. 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.

  • the degree is one, because both climbers can only return down the mountain.

  • At a vertex where one climber is at a peak or a valley and the other one is not, then the degree is 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 climbers 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.

  • is not connected.)

According to the handshaking lemma must contain a path. That path tells how to coordinate the climbers' movement to the summit.

It has been observed that for a mountain with 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 .

would not be a finite graph, so the handshaking lemma might be connected but only by a path with an infinite number of vertices, possibly taking the climbers "infinite time" to traverse.

Infinite number of peaks and valleys

The following result is due to :

  1. are continuous functions, and such that neither function is constant on an interval" stands for a composition of functions.

. .

Notes

References

  • .

  • .

  • .

  • .

  • .

  • .

  • .

  • .

  • .

  • .

  • .

  • .

  • .

  • ..