The Parallel Mountain Climbers Problem

Consider the following problem:

Given a mountain range, as in figure 1, we ask if it is possible for two climbers, Alice and Bob, starting at points A and B, to meet each other by traversing the mountain range in such a way that they maintain the same altitude at all times.

First, we must define what we mean by a mountain range. Informally, we think of a mountain range simply as a series of alternating peaks and valleys. Furthermore, we require that the endpoints of the mountain range are at the same level (say, sea level) and that no valley goes lower than sea level. We can make this definition more formal, but it requires some tedious notation.

A Little Graph Theory

Next, we will simplify the situation by relating this problem to a question about graphs. Given a mountain range, we will construct an associated graph and then rephrase our original problem as a question about this graph. But first, we need an intermediary step (see figure 2).

Wherever there is a peak or a valley, we draw a horizontal line through it, which extends across the entire range. Label the intersections of these horizontal lines and the mountain range.

The vertices of our graph will be ordered pairs of points, (X, Y), on the same horizontal line such that

  1. at least one of X or Y is a peak or valley
  2. X is to the left of Y
These vertices will represent possible pairs of positions that Alice and Bob may occupy. Namely, the vertex (X, Y) will represent the configuration where Alice is at position X and Bob is at position Y.

There is an edge between two vertices (X1, Y1) and (X2,Y2) if and only if Alice and Bob, starting at locations X1 and Y1 respectively, may move constantly in the same directions (ie: both going up or both going down) to locations X2 and Y2. Notice that since Alice and Bob can travel at arbitrary speed, this condition implies that, as they proceed from (X1, Y1) to (X2, Y2), they may maintain the same altitude.

The graph in figure 3 corresponds to the mountain range in figure 2.

So, what is the relation of this graph to our problem? The starting position corresponds to the vertex (A, B) on our graph. Further, the two climbers will meet if they are at a vertex of the form (X, X). Finally, Alice will meet Bob if and only if there is a path from (A,B) to one of the desired vertices. Thus, we have to show that, given any mountain range, its associated graph has such a path.

A Theorem

Now we need some results about graphs:

Theorem: In any graph G, the sum of the degrees of all the vertices in G is equal to twice the number of edges in G.

Proof: Each edge corresponds to two vertices, one at each end. Hence, by summing the degrees of the vertices, we count each edge twice: once for each endvertex.

Corollary: In any graph, the number of vertices with odd degree is even.

Proof: The sum over all degrees is even, by the above theorem. Thus, the number of odd terms (ie: vertices of odd degree) in the sum is even.

Apply the Theorem

Now, we examine the degrees of the graph associated with a mountain range. Consider a given vertex (X, Y). We have the following cases:

Case 1: X=A, Y=B.
There is only one choice from the starting postion, so this vertex has degree one.

Case 2: X is a peak or a valley, and Y is a peak or a valley, respectively.
Without loss of generality, assume that both X and Y are peaks. Once Alice is at postion X she can follow the left path or the right path down. Similarly, Bob has the same choices. Thus, looking at vertex (X, Y), 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: X is peak or a valley, Y is a valley or a peak, respectively.
Clearly, any vertex of this form has degree zero since the climbers could neither reach nor leave it.

Case 4: Either X or Y is not a peak or valley.
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 5: X=Y.
These configurations correspond precisely to the situations where Alice and Bob may meet. Assume without loss of generality that they meet at a peak. From this configuration, Alice and Bob may leave the peak together or they may split up. If they stay together, we have two possibilites: they both go left or they both go right. If they split up, we have only one possibility: Alice goes left and Bob goes right. This fact arises from our definition of which positions constitute vertices. We only allow situations where Alice is to the left of Bob. So, vertices of the form (X, X) have degree 3, unless X=Y=A or X=Y=B in which case it is clear that (A,A) and (B,B) have degree 1.

The Punchline

Our graph may have many components, but we are only concerned with the one containing (A, B). Let C be the component containing (A, B); we treat C as a graph in its own right. As noted in Case 1, (A, B) has odd degree. However, by the above Theorem, we need at least one other vertex of odd degree in C. But, the only other vertices of odd degree are of the form (X, X). Hence, there is a path from (A, B) to some vertex of the form (X, X). In other words, the answer to the question we asked at the beginning is:

"Yes, Alice and Bob can meet and live happily ever after."

The Applet

Here's a little applet to illustrate the Parallel Mountain Climbers Problem.
  1. Enter a mountain range by specifying the peaks and valleys, in order from left to right (no more than 100 points, please). Make sure that you alternate peaks with valleys. The applet will not let you enter an invalid mountain range.
  2. Press GO to send Alice and Bob on their way or press STEP to move step by step.
  3. Press CLEAR to begin again.
Your browser does not support Java, or Java is not enabled.

This problem is described in Math Horizons, November 1995 by Alan Tucker. It is also mentioned in the book Introduction to Graph Theory (Prentice-Hall) by Douglas B. West as exercise 1.3.10 where it is attributed to D. Hoffman.
This page is presented to Prof. Godfried Toussaint as a Web project for the course 308-507A Computational Geometry by Kevin D'Aguiar and Marcus Hum.