Misplaced Pages

Mountain climbing problem

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
Mathematical problem
A trivial example.

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. 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, various planar motion planning problems in computational geometry, the inscribed square problem, semigroup of polynomials, 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.

Analysis

The problem can be rephrased as asking whether, for a given pair of continuous functions f , g {\displaystyle f,g} with f ( 0 ) = g ( 0 ) = 0 , f ( 1 ) = g ( 1 ) = 1 {\displaystyle f(0)=g(0)=0,f(1)=g(1)=1} (corresponding to rescaled versions of the left and right faces of the mountain), it is possible to find another pair of functions x 1 , x 2 {\displaystyle x_{1},x_{2}} with x 1 ( 0 ) = x 2 ( 0 ) = 0 , x 1 ( 1 ) = x 2 ( 1 ) = 1 {\displaystyle x_{1}(0)=x_{2}(0)=0,x_{1}(1)=x_{2}(1)=1} (the climbers' horizontal positions at time t {\displaystyle t} ) such that the function compositions f ∘ x 1 {\displaystyle f\circ x_{1}} and g ∘ x 2 {\displaystyle g\circ x_{2}} (the climbers' altitudes at time t {\displaystyle t} ) are the same function.

Finite number of peaks and valleys

An example requiring backtracking. The original image is an animated SVG; click through to view it.

When f , g {\displaystyle f,g} 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 G {\displaystyle G} with one vertex labeled ( x 1 , x 2 ) {\displaystyle (x_{1},x_{2})} whenever f ( x 1 ) = g ( x 2 ) {\displaystyle f(x_{1})=g(x_{2})} and either f ( x 1 ) {\displaystyle f(x_{1})} or g ( x 2 ) {\displaystyle g(x_{2})} 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.

  • At the vertex ( 0 , 0 ) {\displaystyle (0,0)} , the degree is one: the only possible direction for both climbers to go is onto the mountain. Similarly, at ( 1 , 1 ) {\displaystyle (1,1)} 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.
  • At a vertex where one climber is at a peak and the other is at a valley, the degree is zero: such positions are unreachable. (That is, if such a vertex exists, then the graph G {\displaystyle G} is not connected.)

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 in all of G {\displaystyle G} are ( 0 , 0 ) {\displaystyle (0,0)} and ( 1 , 1 ) {\displaystyle (1,1)} , these two vertices must belong to the same connected component. That is, G {\displaystyle G} must contain a path from ( 0 , 0 ) {\displaystyle (0,0)} to ( 1 , 1 ) {\displaystyle (1,1)} . 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.

This technique breaks down when f , g {\displaystyle f,g} have an infinite number of local extrema. In that case, G {\displaystyle G} would not be a finite graph, so the handshaking lemma would not apply: ( 0 , 0 ) {\displaystyle (0,0)} and ( 1 , 1 ) {\displaystyle (1,1)} 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 Huneke (1969):

Suppose f {\displaystyle f} and g {\displaystyle g} are continuous functions from [ 0 , 1 ] {\displaystyle } to [ 0 , 1 ] {\displaystyle } with f ( 0 ) = g ( 0 ) = 0 {\displaystyle f(0)=g(0)=0} and f ( 1 ) = g ( 1 ) = 1 {\displaystyle f(1)=g(1)=1} , and such that neither function is constant on an interval. Then there exist continuous functions s {\displaystyle s} and t {\displaystyle t} from [ 0 , 1 ] {\displaystyle } to [ 0 , 1 ] {\displaystyle } with s ( 0 ) = t ( 0 ) = 0 {\displaystyle s(0)=t(0)=0} , s ( 1 ) = t ( 1 ) = 1 {\displaystyle s(1)=t(1)=1} , and such that f ∘ s = g ∘ t {\displaystyle f\circ s\,=\,g\circ t} , where " ∘ {\displaystyle \circ } " stands for a composition of functions.

On the other hand, it is not possible to extend this result to all continuous functions. For, if f {\displaystyle f} has constant height over an interval while g {\displaystyle g} 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. James V. Whittaker (1966) gives a concrete example involving x sin ⁡ ( x − 1 ) {\displaystyle x\sin(x^{-1})} .

Notes

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

References

External links

Categories: