Hikers Meeting in the Middle

Question

Two hikers are separated by a two-dimensional mountain range, like the one shown below. The mountain range alternates between peaks and valleys, connected by straight lines.

Both hikers are at sea level, and the mountain range never dips below sea level.

The two hikers want to meet up with each other. Prove that they can do this while staying at the same altitude as each other for their entire journey. They are allowed to backtrack.

Source: http://www.cs.cmu.edu/puzzle/puzzle12.html

Answer 1

I think @Sleafar's deleted answer works:

Put the hikers and the mountains in a big swimming pool. The hikers will always swim at the water level which we will change.

Start increasing the water level until one hiker reaches a local peak. The hiker that reached the peak will now descend on the other side of the mountain. Decrease the water level until one hiker reaches a valley. This hiker will now ascend the next mountain.

Whenever one hiker reaches a peak or a valley, we reverse the water direction and the hiker continues on the other side of the peak or valley, while the other hiker reverses direction. (If both hikers encounter a peak or valley at the same time, they both continue in the same direction as before.)

This process is the same in reverse. Because it can be reversed without ambiguity, it is impossible to get stuck in a cycle.

Suppose the process ever returns to the starting state. Then, we can run it backwards and it will look exactly the same as it did forwards. Then, exactly halfway through, both hikers must reverse direction at the same time, which is impossible.

Because the procedure cannot be stuck in a loop, and it can't return to the starting state, it must end with at least one hiker reaching the opposite side (in fact, they both reach the opposite side, but we don't need to prove this). This guarantees that the hikers meet at some point.

Answer 2

Suppose we reformulate the problem as follows. I apologize for the mathematical jargon; the essential idea is that we are to consider the set of legal positions for the two hikers, and show that the initial position is reachable from the position with the hikers reversed. We do this by showing, in a precise sense, that nothing disconnects them.

To start out, let us make a definition:

Let $f:[0,1]\rightarrow \mathbb [0,\infty)$ be a continuous* function with $f(0)=f(1)=0$, representing the height of the mountain range a given distance from the left. Assume that the hikers begin at $0$ and $1$ respectively. Next, let $S=[0,1]\times[0,1]$ be the unit square, which is the set of tuples $(x,y)$ of possible positions of the hikers. Define the difference in height $g$ as: $$g(x,y)=f(x)-f(y).$$ Note that the legal positions are exactly those for which $g(x,y)=0$.

We want to know if there is a path with $g(x,y)=0$ throughout starting at $(1,0)$ and ending at $(0,1)$. This is equivalent to saying the hikers may meet (as they will meet in the middle when they swap positions like in this example). The only way this could fail to happen is if there is some path of illegal positions $\gamma$ running from $(1,x)$ or $(x,1)$ to a position of $(0,x)$ or $(x,0)$, which would divide the square suitably. Notice, moreover, that $g(1,x)\leq 0$ and $g(0,x)\leq 0$ whereas $g(x,1)\geq 0$ and $g(x,0)\geq 0$. As the sign of $\gamma$ must not change due to the intermediate value theorem, it either runs bottom to top or left to right. However, this is impossible as it must then intersect the line $x=y$, along which $g(x,y)=0$, which must not be true of any point on $\gamma$. Therefore, no path of illegal positions divides the space into two parts, and there is thus, to the contrary, a path from $(0,1)$ to $(1,0)$, as desired.

(*I will admit I have no proof in mind to show that "two points in a closed set in $S$ are disconnected if only if a path in the complement divides them." Maybe someone who wants to do some analysis can fill this in. In the piecewise case, we can, with some reductions, work on a discrete grid rather than the unit square and the proof is obvious there)

Answer 3

Alright, let's call the person on the left Alice, and the person on the right Bob.

The conditions that make it possible for them to be at the same altitude until they meet are:

• the first peak that Alice encounters is higher than the first peak that Bob encounters
• the bottom of the first valley that Bob encounters is the lowest non-sea level valley on the graph, and the second peak that he encounters is the highest point on the graph. Therefore, this slope encompasses every possible altitude in the mountain range, except for sea level.

Therefore, the solution:

1. Bob climbs to his first peak; Alice matches his altitude
2. Bob descends to his first valley; Alice goes back down the mountain, matching his altitude
3. Alice proceeds to the right; Bob simply matches her altitude the whole way by traversing the slope between his first valley and second peak, until Alice reaches her fourth mountain, which Bob is on the other side of, and they both ascend to meet at the peak.

Answer 4

At each given time we should only care about the next peak or valley of each of the hikers(let's call them Bruce B. and Tony S.). There are 3 possibilities:

1. The next peak of Bruce B. is higher than the next peak of Tony S.
2. The next peak of Bruce B. is lower than the next peak of Tony S.
3. The next peaks are equally high

In case 1: Tony S. would climb up his peak and Bruce B. would go just as high. Then Tony S. would move to the valley while Bruce B. continues his backtracking descent

In case 2: Bruce B. would climb up his peak and Tony S. would go just as high. Then Bruce B. would move to the valley while Tony S. continues his backtracking descent

In case 3: They both go to the next peak and:

• Either they meet(if it was the only remaining peak between them)
• Or they look at the next peak and repeat the steps

So basically, the one whose next peak is higher will have to backtrack, letting the other one move forward.

Using this strategy they will eventually meet either:

• On the highest peak
• Or on the highest point between 2 highest peaks

Answer 5

Let's take a peak diagram of:

             B 
            /\            C
           /  \          /\
    A     /    \        /  \
   /\____/      \      /    \
  /              \____/      \
1/                            \2

The steps would be:

• 1 to A
• 1 down, then up towards B
• 2 hits C, goes down, 1 goes down
• 1 hits valley, goes back up to A, down until 2 can hit valley
• 1 goes up to B, 2 goes up to B

Another way of looking at it is: 1-Peak, 1-Valley, 2-Peak, 1-Valley, 1-Peak, 2-Valley, 1-Peak, 1-Valley, 12-Final

Let's try to factor in direction (Forward is towards highest peak): 1-Peak(F-F), 1-Valley(F-A), 2-Peak(F-F), 1-Valley(A-F), 1-Peak(A-A), 2-Valley(A-F), 1-Peak(F-F), 1-Valley(F-A), 12-Final(F-F)

So I don't know if there's a good way of determining which peak/valley to go to.

I would say that it looks like you take the current altitude span (e.g. 2 to C initially vs 1 to A initially) and see if the entirety of the other's route falls into it. Then take the next span (C to valley) and see how much of the other's span falls into that altitude.