The Two Men of Tibet

Two men are located at opposite ends of a mountain range (in Tibet or elsewhere), at the same elevation. If the mountain range never drops below this starting elevation, is it possible for the two men to walk along the mountain range and reach each other's starting place, while always staying at the same elevation? [Zeitz, pp. 126-128]

If need be, i.e. in order to maintain the same elevation, the men may have to retrace their steps, so the speed is not an issue here.

(The applet represents the mountain range as a piece-wise linear function, a broken line. The line can be modified by dragging any of its points up or down. Due to programming issues, the applet will ask for plateaus, if there are any, to be removed. The positions of the two men are shown as dots: a white dot and a black dot. "Delay" is the number of milliseconds the fellows spend catching their breath between any two steps.)

This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at https://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet.

What if applet does not run?

Solution

References

P. Zeitz, The Art and Craft of Problem Solving, John Wiley & Sons, 1999

Solution

The problem has an elegant, almost elementary solution based on graph theory.

First, note all the "corner" points, the vertices of the broken line. Through these draw horizontal lines and mark their intersections with the segments forming the broken line. Denote them A, B, C, ..., X, W, Z and call them named.

Now we shall create a graph whose nodes are ordered(!) pairs of the named points: (A, A), (A, B), ..., (A, Z), ..., (Z, Z). We include only those pairs in which at least one of the components corresponds to a vertex of the broken line. For example, (F, U) is included, while (F, J) is not. Think of the nodes as possible locations of the two men during their journey. We add an edge between two nodes iff it is possible for the men to move from one to the other in "one step". For example, (F, U) and (C, R) become connected, whereas (F, U) and (G, O) do not.

We also disallow edges in the form (x, x) - (y, y), for two successive vertices x and y. The fellows move in different directions so that, while each may retrace his steps, there is no need for them to travel alongside each other. The two may only meet at a local extrema where they swap the sides of the broken line leading to that vertex and continue in different directions. (Vermont Rutherfoord informed me that during a presentation Dr. Stephen Locke made an observation that showed the need for this stipulation.)

To solve the problem we have to show that there exists a path from (A, Z) to (Z, A). The existence of such a path follows from the following assertions:

The only vertices of the graph of odd degree are (A, Z) and (Z, A).
All other vertices have an even degree.

(Vermont Rutherfoord has observed that the degree of (A, Z) and/or (Z, A) is 1 except when either A or Z lie on a plateau.)

Consider a path on the graph that starts with (A, Z). Make it as long as possible. As a subgraph, it satisfies the Handshake Lemma. We may assert that the sum of degrees of all the nodes on the path is even. Since it includes a node (A, Z) of odd degree, it must include another node of odd degree, but there is only one such node: (Z, A). Hence the latter is also in the path. It's its other endpoint.

Remark

In a book published on occasion of G4G4 (Gathering for Gardner #4), N. J. de Bruijn described and outlined a solution to a slightly different problem wherein the two men move along separate paths. The solution is virtually the same and relies on the Handshake Lemma.

References

N. J. de Bruijn, The Beer Bottles Problem, in Puzzles' Tribute: A Feast for the Mind, (D. Wolfe, T. Rodgers, Eds), A K Peters, 2002

71547131