Mountain climbing problem

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

When ${\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.[6] This can be shown by drawing out a sort of game tree: an undirected graph ${\displaystyle G}$ with one vertex labeled ${\displaystyle (x_{1},x_{2})}$ whenever ${\displaystyle f(x_{1})=g(x_{2})}$ and either ${\displaystyle f(x_{1})}$ or ${\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 ${\displaystyle (0,0)}$, the degree is one: the only possible direction for both climbers to go is onto the mountain. Similarly, at ${\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 ${\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 ${\displaystyle G}$ are ${\displaystyle (0,0)}$ and ${\displaystyle (1,1)}$, these two vertices must belong to the same connected component. That is, ${\displaystyle G}$ must contain a path from ${\displaystyle (0,0)}$ to ${\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.[1]

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

The following result is due to Huneke (1969):

Suppose ${\displaystyle f}$ and ${\displaystyle g}$ are continuous functions from ${\displaystyle [0,1]}$ to ${\displaystyle [0,1]}$ with ${\displaystyle f(0)=g(0)=0}$ and ${\displaystyle f(1)=g(1)=1}$, and such that neither function is constant on an interval. Then there exist continuous functions ${\displaystyle s}$ and ${\displaystyle t}$ from ${\displaystyle [0,1]}$ to ${\displaystyle [0,1]}$ with ${\displaystyle s(0)=t(0)=0}$, ${\displaystyle s(1)=t(1)=1}$, and such that ${\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 ${\displaystyle f}$ has constant height over an interval while ${\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.[6] James V. Whittaker (1966) gives a concrete example involving ${\displaystyle x\sin(x^{-1})}$.[6]