This problem was first posed by James Whittaker in 1966 (you can ch...
In mathematical terms the problem can be re-written as: Let $s(\...
When one or two of the climbers hit a critical point (peak or valle...
The sum of all the degrees of a graph $D_{Total}$ is composed by th...
In this paper we prove that the parallel climbers problem has a sol...

Discussion

The sum of all the degrees of a graph $D_{Total}$ is composed by the sum of all the degrees of even degree vertices $D_{even}$ and the sum of all the degrees of odd degree vertices $D_{odd}$ $$ D_{Total}=D_{even}+D_{odd} $$ We know from the previous theorem that $D_{Total}$ is an even number and at the same time $D_{even}$ is a sum of even numbers and so $D_{even}$ is also even. Even numbers can be written in the form $2k$ and odd numbers can be written in the form $2k+1$ where $k$ is an integer. If $D_{odd}$ was an odd number: $$ D_{odd} + D_{even} = (2k+1) + (2m) =2(k+m)+1=D_{Total} $$ which means that we would reach a contradiction and $D_{Total}$ would be odd. We conclude that $D_{odd}$ is always an even number! In this paper we prove that the parallel climbers problem has a solution if the sides of the mountain are piecewise monotone. In fact the problem in general doesn't have a solution. For instance if the 2 sides of the mountain have the following profile, one is constant in an interval and the other one oscillates around a value there's no solution to the problem. ![](http://i.imgur.com/QCJOOZJ.png) Tamás Keleti proved in 1993 that the parallel climbers problem has a solution if neither of the profiles has an interval of constancy. Keleti's proof doesn't require the profiles to be piecewise linear. In mathematical terms the problem can be re-written as: Let $s(\tau)$ and $s'(\tau')$ be continuous, piecewise linear functions from $[0,1]$ to $[0,1]$, with $s(0)=s'(0)=0$ and $s(1)=s'(1)=1$ (prime doesn't mean differentiation here). Then there exist two other continuous piecewise linear functions $$ \tau(x),\tau'(x):[0,1]\rightarrow[0,1] $$ such that $$ \tau(0)=\tau'(0)=0\\ \tau(1)=\tau'(1)=1 \\ s(\tau(x))=s(\tau'(x)) \text{ for every } x \in [0,1] $$ In other words, if Alice and Bob are the mountain climbers it means that they each start at time 0 and height 0 and want to wind up at time 1 and height 1, maintaining the same height (s) as they move. This problem was first posed by James Whittaker in 1966 (you can check the original paper [here](http://cms.math.ca/openaccess/cjm/v18/cjm1966v18.0873-0882.pdf)). Here we can see an illustration of the problem: ![](https://upload.wikimedia.org/wikipedia/commons/7/76/Mountain_climbing_problem.gif) It's relatively easy to coordinate the movement of the 2 climbers when they are not at peaks nor valleys. The problem is that in order to make it to the top of the mountain the climbers will eventually have to go down the mountain in order to always be at the same height. 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. These complications make the problem unintuitive and sometimes rather difficult, both in theory and in practice. When one or two of the climbers hit a critical point (peak or valley) there are basically 4 different situations: **Case 1** ![](http://i.imgur.com/UmTdlsE.png) When the 2 climbers are at interior points of the linear segments then they can each move in 2 directions (both forward/backward if the segments have the same monotonicity or one forward/backward and the other backward/forward if the segments have opposite monotonicity). This vertex has degree 2 (a degree of a vertex is the number of edges incident to that vertex) **Case 2** ![](http://i.imgur.com/rZtPHnV.png) Once Alice is at position A she can follow the left path or the right path down. Similarly, Bob has the same choices. Thus, looking at vertex (A, B), the edges coming out correspond to both going to the left, both going to the right, and the two cases where they head in opposite directions. We conclude that this vertex must have degree four. **Case 3** ![](http://i.imgur.com/fJIO3ii.png) Without loss of generality, we can assume Alice is at a peak and Bob has climbed up and stopped before his peak. Symmetric arguments will hold for all other cases. Well, Alice has the choice of left or right, but she must climb downwards. So Bob has no choice. Thus any vertex in this case will have degree 2. **Case 4** ![](http://i.imgur.com/G6Cxlya.png) Clearly, any vertex of this form has degree zero since the climbers could neither reach nor leave it.