Topology

Two climbers who must stay level

Two climbers start at opposite ends of a mountain range and want to meet, but they are roped so that they must always be at exactly the same height. Can they always do it? Yes, for any range with finitely many peaks — and the proof is a count of ways out. Draw every pair of positions at equal heights as a graph: every point has an even number of ways out except the four corners, and the symmetry of swapping the climbers does the rest. The route can be long: two peaks force four turns back, eight peaks about forty-seven.

Worth reading first: Three colours force a triangle · A board that cannot be drawn.

Two climbers stand at the two ends of a mountain range, both at sea level, and want to meet somewhere on it. They are tied together by a rope that forces them to stay at exactly the same height at every moment — when one goes up, the other must go up; when one stands on a peak, the other must be at a point of exactly that height. Each may walk forwards or backwards along the range as often as needed, but neither may jump. Can they always meet?

For a range with a single peak the answer is obviously yes: both walk uphill and meet at the top. For a range with two peaks of different heights it is less obvious. The climber facing the lower peak reaches it while the other is still climbing; the first must now go down the far side, and the other, to stay level, must go back down too. The question was studied by James Whittaker and John Huneke in the 1960s, and the answer is that the climbers can always meet, provided the range has only finitely many peaks and valleys. The proof, like three colours force a triangle’s proof of Sperner’s lemma, is a count: it shows that a path must exist by showing that the places where one could get stuck come in pairs.

Every place two climbers can stand level

Every place two climbers can stand at one height. 171 vertices, 176 edges, route 50 legs, 12 reversals
Fig. 1 A mountain range and every pair of positions at which the two climbers stand at one height. The graph has odd degree only at its four corners, so the start (0, 1) is joined to the finish (1, 0). The orange path is a shortest route.

Measure positions along the range from 0 at the left end to 1 at the right, and let f(x)f(x) be the height at position xx. A state of the two climbers is a pair (x,y)(x, y) — the left climber at xx, the right at yy — and the rope requires f(x)=f(y)f(x) = f(y). So the climbers’ possible states are the set of points in the unit square where f(x)=f(y)f(x) = f(y). They start at (0,1)(0, 1) and want to reach a point where x=yx = y, or equivalently, by continuing past each other, the opposite corner (1,0)(1, 0), where they have swapped ends.

For a range made of straight slopes, this set is a graph: a finite collection of straight segments joined at their ends. Cut the range at every height where some peak or valley lies. Between two consecutive such heights, each slope of the range crosses the band once, rising or falling in a straight line; pairing any slope with any other gives a segment of states in which both climbers traverse their slopes, staying level. The ends of these segments are the states where both climbers are at a critical height. The hero builds the graph for a range with four peaks, finding 171 positions and 176 segments, and draws it in the square, with the diagonal x=yx = y — the states where the climbers stand together — in blue.

The climbers’ problem is now a question about a graph: is there a path from the corner (0,1)(0, 1) to the diagonal, or to the opposite corner? The orange path in the hero is one, found by searching the graph, and it is a shortest route in the number of segments. Along it the climbers move continuously and stay level, which the next figure checks.

A journey with turning back

Two climbers turning back to stay level. 0.000/1.000 0.023/0.972 0.045/0.944 0.080/0.903 0.102/0.875 0.080/0.839 0.045/0.786 0.023/0.750 0.045/0.729 0.080/0.698 0.102/0.677 0.125/0.656 0.161/0.677 0.196/0.698 0.250/0.729 0.277/0.698 0.295/0.677 0.313/0.656 0.339/0.625 0.313/0.571 0.295/0.536 0.277/0.500 0.295/0.477 0.313/0.455 0.339/0.420 0.375/0.375 0.420/0.339 0.455/0.313 0.477/0.295 0.500/0.277 0.536/0.295 0.571/0.313 0.625/0.339 0.656/0.313 0.677/0.295 0.698/0.277 0.729/0.250 0.698/0.196 0.677/0.161 0.656/0.125 0.677/0.102 0.698/0.080 0.729/0.045 0.750/0.023 0.786/0.045 0.839/0.080 0.875/0.102 0.903/0.080 0.944/0.045 0.972/0.023 1.000/0.000
Fig. 2 The two climbers’ positions along the range through the 50 legs of a shortest route, and their common height. They turn back 12 times between them.

Follow the route as a journey. The figure plots the left climber’s position, the right climber’s position and their common height through the route’s 50 legs. The two positions start at 0 and 1 and end swapped, crossing in the middle where the climbers meet. In between, the positions wander: each climber turns back repeatedly, 12 times between them, as the route threads through the graph. The common height rises and falls with them. The figure’s checks interpolate along every leg and confirm that the two heights agree everywhere, not only at the corners of the legs.

The turning back is forced. The right climber reaches the nearer peak first: it stands at 0.45, while the left climber, at the same height, is still partway up the first slope, which rises to 0.55. The right climber cannot go higher, so the only way on is down the far side of its peak, into the valley at 0.1; the left climber must go back down too, towards the start, to stay level. Only when both are at 0.1 can they turn round together — the right climber up the next peak, of height 0.7, the left back up its first slope — and when the left climber reaches its summit at 0.55, the right one is again partway up a slope, and the exchange repeats in the other direction. Every peak lower than the heights around it costs a pair of reversals, and the order of the peaks’ heights, more than their number, decides how tangled the route is.

Why every position but the corners has an even number of ways out

Why every position but the corners has an even number of ways out. deg 1: 4; deg 2: 160; deg 4: 7
Fig. 3 The number of ways out of each position: up·up plus down·down. Every position has 2 or 4 ways out except the four where both climbers stand at ends, which have one.

The proof that a route always exists rests on counting the ways out of each position in the graph. A climber standing on a slope at a critical height can go up or down — one way each. A climber on a peak can only go down, by either side — two ways down, none up. A climber in a valley has two ways up and none down. A climber at an end of the range can only go up, one way. Since the climbers must move up together or down together, the number of segments leaving a position (x,y)(x, y) is

up(x)⋅up(y)+down(x)⋅down(y).\text{up}(x) \cdot \text{up}(y) + \text{down}(x) \cdot \text{down}(y).

The figure tabulates the cases. Two climbers on slopes: 1⋅1+1⋅1=21 \cdot 1 + 1 \cdot 1 = 2. A climber on a peak beside one on a slope: 0⋅1+2⋅1=20 \cdot 1 + 2 \cdot 1 = 2. Two on peaks: 0+2⋅2=40 + 2 \cdot 2 = 4. Two in valleys: 2⋅2+0=42 \cdot 2 + 0 = 4. A peak and a valley cannot be at the same height when all the critical heights differ. And two climbers at ends: 1⋅1+0=11 \cdot 1 + 0 = 1. So every position has an even number of ways out except the four where both climbers are at ends — (0,0)(0, 0), (1,1)(1, 1), (0,1)(0, 1) and (1,0)(1, 0) — which have exactly one. The hero’s range has 4 positions of degree 1, 160 of degree 2 and 7 of degree 4, and the figure’s checks confirm the formula at every one.

Now apply the handshake rule. In any piece of a graph the number of positions with an odd number of ways out is even, since every segment has two ends and the total count of segment-ends is twice the number of segments. So the piece containing the start (0,1)(0, 1) must contain another odd position — one of (0,0)(0, 0), (1,1)(1, 1) or (1,0)(1, 0). If it is (1,0)(1, 0), the climbers can swap ends and so certainly meet. If it is (0,0)(0, 0), the diagonal: but the graph is symmetric under swapping xx and yy, since f(x)=f(y)f(x) = f(y) is the same equation as f(y)=f(x)f(y) = f(x), so the mirror image of the path from (0,1)(0, 1) to (0,0)(0, 0) is a path from (1,0)(1, 0) to (0,0)(0, 0), and joining them gives a path from (0,1)(0, 1) to (1,0)(1, 0) anyway. The same holds for (1,1)(1, 1). Either way the start and the finish lie in one piece, and there is a route.

That is the entire proof, and it never constructs the route. It shows that a walk from the start, never reusing a segment, cannot get stuck except at another odd position — at every position of even degree there is always a way out not yet used — and that the only odd positions it can reach lead to a meeting. A board that cannot be drawn used the same argument for the game of Hex, walking along the boundary between colours until it emerges at a corner; Sperner’s lemma uses it to walk through a triangulation to a three-coloured triangle. All three are the observation that a path through a graph with even degrees everywhere else must end at an odd vertex.

The smallest ranges

The smallest ranges that make climbers turn back. 0,0.8,0 | 0,0.5,0.2,0.9,0 | 0,0.9,0.2,0.5,0
Fig. 4 Three small ranges and their graphs. With one peak the route goes straight across; with two peaks of different heights it turns back four times.

The small cases make the structure plain. A single peak gives a graph with just the diagonal and a single path from (0,1)(0, 1) to (1,0)(1, 0) through the summit: both climbers walk up, meet at the top, and could continue down the far sides to swap ends. No turning back is needed.

Two peaks give the first interesting graph. With the higher peak on the right, the left climber reaches the lower peak first and must descend into the valley while the right climber backs down the slope of the higher peak; once both are at the valley’s height, the left climber climbs the higher peak while the right climber comes back up and over the lower one. The route turns back four times, and in the random ranges below, every one of the 200 two-peak ranges needs exactly four reversals on a shortest route. Which peak is higher changes the shape of the route but not the count, as the second and third panels show: the two graphs are mirror images, and their routes are too.

The graphs also contain more than the route. Besides the path from corner to corner there is the diagonal, where the climbers stand together, with branches leaving it wherever both could step apart while staying level, and on larger ranges there are pieces of the graph that the route never touches. The parity argument guarantees that a route exists without saying which branches lead to it; a search through the graph is what finds it.

More peaks, more turning back

More peaks, more turning back. 1: rev 0.00 legs 2.0; 2: rev 4.00 legs 10.0; 3: rev 8.60 legs 25.2; 4: rev 15.04 legs 51.0; 5: rev 20.96 legs 84.6; 6: rev 28.24 legs 131.5; 8: rev 47.08 legs 276.8
Fig. 5 For 200 random ranges at each count of peaks, the average number of times the climbers turn back on a shortest route. One peak needs none; every two-peak range needs four; the count grows faster than the number of peaks.

The theorem says the climbers always meet. It does not say how much walking they need, and the figure measures that for random ranges, drawing 200 ranges with each number of peaks from one to eight, building each graph, finding a shortest route and counting reversals. The average rises from 0 for one peak and exactly 4 for two to 8.6 for three, 15.0 for four, and 47.1 for eight. The number of legs grows faster still, from 2 for one peak to about 277 for eight.

The growth reflects the graph’s size. A range with kk peaks has about 2k2k critical heights, and at each height the number of points of that height is roughly proportional to kk, so the graph has a number of positions growing like k2k^2 per height and k3k^3 in all. A shortest route through such a graph may visit a sizeable fraction of it, and the counts in the figure are consistent with reversals growing roughly like the square of the number of peaks. Across all 1,400 random ranges, every graph has exactly four odd positions, and every route is found — the theorem holds every time, as it must.

Where the argument needs finitely many peaks

Every place two climbers can stand at one height. 333 vertices, 340 edges, route 82 legs, 16 reversals
Fig. 6 A range with five peaks and its graph of equal heights. The route is longer, the graph has more loops, and still only its four corners have an odd number of ways out.

The argument used one assumption heavily: the range is made of finitely many straight slopes, so that the set of equal-height positions is a finite graph with a well-defined number of ways out of every position. For a smooth range with finitely many peaks and valleys the same reasoning works after a little care, since each monotone stretch can be treated like a straight slope. The figure draws a five-peak range, whose graph is visibly more tangled than the hero’s, and the degree census still finds odd positions only at the four corners.

Without the finiteness the theorem can fail. If the range wiggles infinitely often — a profile with infinitely many tiny peaks accumulating at a point — the equal-height set is no longer a graph, the degree count has nothing to count, and examples are known in which the climbers cannot meet at all, even though the profile is continuous. Continuity alone is not enough; what the proof needs is that the profile is piecewise monotone. That is the same distinction where the fixed point escapes drew for Brouwer’s theorem, which fails when one of its hypotheses is dropped and fails in a specific, constructible way.

A one-dimensional theorem that needed two dimensions

It is worth noticing what kind of theorem this is. It is about a single function on an interval, and the simplest theorems of that kind — that a continuous function changing sign has a zero, that something always stays put when an interval is mapped into itself — are proved by following the function along the line until something must happen. The climbers’ theorem cannot be proved that way. The two climbers move independently, so the natural setting is the square of their positions, and the proof is a statement about a curve in that square: the set where f(x)−f(y)=0f(x) - f(y) = 0.

That move, from a statement about one function to a statement about a set in the plane, is the same one that two opposite points that agree twice made for the Borsuk–Ulam theorem, where a fact about a single function on a circle — two opposite points with equal values — became a fact about the zeros of f(x)−f(x+π)f(x) - f(x + \pi). In both, the function of two variables is antisymmetric under a swap, and the swap symmetry is what the proof uses at the decisive moment: here, to rule out the possibility that the start is joined only to the diagonal.

The parity count itself belongs to a larger family. A count of ways out that is even everywhere except at a few marked points forces those points to be joined in pairs, and the same principle, made into a number, is the degree that a number that counts what it cannot see used to detect fixed points from a map’s effect on holes. A twist that cannot avoid two points needed an argument of the same kind to show that a twist of an annulus fixes at least two points rather than one: once a count is known to be even, a single solution forces a second. For the climbers the count is of segments at each position, and the solution it forces is a route.

What the climbers’ theorem shares with none of these is how little continuity it needs. A slope can swing but never jump showed that a derivative must satisfy the intermediate value property even when it oscillates wildly; the climbers’ theorem fails for oscillating profiles, because the equal-height set of a wildly wiggling profile is not a graph, and a parity count needs something to count.

What the graph cannot show

The figures show particular ranges and their graphs, and the parity argument proves the theorem for all ranges with finitely many peaks. What the figures cannot show is a shortest route found without the graph: the argument is an existence proof, and the route in each figure was found by searching. Nothing here bounds the length of the shortest route in terms of the number of peaks except crudely, by the size of the graph, and the census measures averages over random ranges rather than the worst case.

The pictures also hide a subtlety in what “meet” means. The climbers meet when they reach the diagonal, and nothing requires that to happen at the highest peak or at any particular place. The theorem says only that they can be in one place at one time; it says nothing about where, and different routes through the same graph can bring them together at different points of the range.

Still open: how long the walk must be

For a range with kk peaks, how many reversals can a shortest route need in the worst case? The random ranges here suggest growth like k2k^2 on average, and simple constructions show that some ranges need many more reversals than random ones do, but an exact formula for the worst case is not something this essay establishes. The problem has relatives in which more than two climbers must stay level, or in which the climbers move on a two-dimensional landscape rather than a line, and for those the parity argument breaks down: with three climbers the set of equal-height states is no longer a graph but a higher-dimensional object, and whether all three can always meet is a different question. Something always stays put began this collection’s account of fixed points with a theorem whose proof, in one dimension, was a single sign change; the climbers’ theorem is the next simplest of the kind, a statement about one line that is proved by turning it into a graph and counting.

Shares its objects with

Essays that name at least two of the same things, and that neither author linked.

Named objects

A dashed tag is an object no other essay names yet.

ContinuityDegreeGraphIntermediate value theoremParityPiecewise-linear