Solution to Problem 209

No correct solutions were received for this problem.

The mountaineers will, indeed, always meet. It's clear that if they must meet at either a peak or a valley. I don't know how to decide this without climbing the mountains and seeing where they meet.

I'll draw two graphs. The first describes the possible positions of the mountaineers, the second their movements between these positions. For the first, draw a horizontal line from each peak and valley (a local maximum or minimum) and mark each intersection of such a line with the mountain range with a vertex as in the figure on the left. Label these vertices a, b,... in order from left to right. I'll call this graph the level graph, L. The set of vertices of the second graph will be the peaks and valleys of L together with {{x,y} | x,y are distinct vertices in L having the same height}; for example, the pairs {c,k} and {d,j} are vertices in V, but {j,m} is not. Draw an edge between two such vertices by saying that

{x,y} is adjacent to {x',y'} if both (i) x and x' are adjacent in L and (ii) y and y' are adjacent in L,
while a peak or valley p is adjacent to {x,y} if x and y are the two vertices of L adjacent to p.

For example, {c,k} is adjacent to {d,j} and to {d,l}; similarly the peak l is adjacent to {k,m}. Let's call this second graph the climbing graph, C. Here are the crucial observations about C.

If a is the first and z the last vertex of L, then {a,z} is adjacent to one vertex of C.
Any peak or valley vertex, p, in C is adjacent to one vertex in C.
Any vertex {x,y} of C different from {a,z} is adjacent to two or four vertices in C.

Let's start climbing! We begin at the vertex {a,z} and move from one vertex of C to another adjacent vertex. Such a move corresponds to the climbers moving along the mountain range while maintaining equal heights. After reaching a vertex of C, we delete the vertex (and the edge) we just came from. Notice that at each stage in the climb, all vertices are adjacent to an even number of vertices, except for any peaks and valleys, and the vertex where we currently sit. We must therefore eventually reach a vertex adjacent to a single other vertex, meaning that the climbers have met at a peak or valley.