## 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.)

What if applet does not run? |

### References

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

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny

### 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:

We also disallow edges in the form

To solve the problem we have to show that there exists a path from

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

### 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

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny