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

Solution

References

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

Copyright © 1996-2008 Alexander Bogomolny

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

First, not 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.

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:

1. The only vertices of the graph with degree 1 are (A, Z) and (Z, A).

2. All other vertices have an even degree.

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 on G4G4 (Gathering four 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

1. 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

Copyright © 1996-2008 Alexander Bogomolny