16
$\begingroup$

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.

enter image description here

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

$\endgroup$
  • 2
    $\begingroup$ I can figure it out intuitively but I haven't the wherewithal to type it all out logically. I like it, though. $\endgroup$ – Engineer Toast Oct 28 '15 at 19:12
  • $\begingroup$ The way the question is worded makes it sound like they aren't allowed to ever go above sea level. Please clarify that they only have to stay at the same altitude as each other. $\endgroup$ – trentcl Oct 28 '15 at 20:33
  • $\begingroup$ The source also provides a solution, in case anyone wants to spoil it for themselves. It's quite elegant, and nicely avoids the problems the currently posted attempts run into. $\endgroup$ – user2357112 supports Monica Oct 28 '15 at 21:21
  • 3
    $\begingroup$ @JacobHolloway: Well, if they meet somewhere else, they can just travel to the middle together. $\endgroup$ – user2357112 supports Monica Oct 29 '15 at 5:23
  • 1
    $\begingroup$ I read about a more general problem on wikipedia once. It's called the mountain climbing problem. en.wikipedia.org/wiki/Mountain_climbing_problem $\endgroup$ – Ben Frankel Oct 29 '15 at 18:47
15
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Take a JonTheMon's picture. The person on the left has to get all the way to the second mountain and then return all the way to the left side of the first mountain. It is not obvious from your strategy how you handle this. $\endgroup$ – Trenin Oct 29 '15 at 12:19
  • $\begingroup$ @Trenin The water level goes up and down several times, and the person on the right reverses direction several times, while the person on the left backtracks. This has no effect on the final result. $\endgroup$ – f'' Oct 29 '15 at 15:09
3
$\begingroup$

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)

$\endgroup$
2
$\begingroup$

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.
$\endgroup$
  • 1
    $\begingroup$ This of course works for this particular image, but I suppose the question was asked in greater generality. It doesn't happen here, but it's not hard to draw examples of mountain ranges which require both Alice and Bob to move backwards at a given point. $\endgroup$ – Fimpellizieri Oct 28 '15 at 20:17
1
$\begingroup$

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
$\endgroup$
  • $\begingroup$ What if you can't backtrack low enough? $\endgroup$ – user2357112 supports Monica Oct 28 '15 at 21:13
  • $\begingroup$ @user2357112 - Provided the mountains never dip below sea level, this should not occur. Since we know they both started at sea level, there will never be a point at which one needs to go lower but the other is unable to. $\endgroup$ – Darrel Hoffman Oct 28 '15 at 21:33
  • $\begingroup$ @DarrelHoffman: Suppose Bruce has a valley of height 4 behind him and a peak of height 8 ahead, while Tony is at a peak of height 6 and has a valley of height 2 ahead of him. $\endgroup$ – user2357112 supports Monica Oct 28 '15 at 21:38
  • $\begingroup$ Bruce will have to backtrack until he gets back down to height 2 so that Tony can get across his valley. We know he can get to height 2 because he started at height 0. Meanwhile, Tony stays on the forward side of his valley, which by definition he can do because Bruce is somewhere between 4 and 2, which is less than 6. $\endgroup$ – Darrel Hoffman Oct 28 '15 at 22:31
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.