Answer to Running Puzzle

Here is the answer to the running puzzle I posted last month:

In short, the simple version of the puzzle is that you are going to run around a track for 30 minutes, at the same time that you know your friend will be doing the same. Your friend goes in 1 direction the whole time, while you may switch directions. You don’t know the location or direction of your friend.  You both run at the same speed. How do you maximize the probability that you’ll meet?

The key to making the puzzle a lot easier is to use the trick that commenter Albert Fuchs suggested, which is to consider the motion from the reference frame of your friend. So, in other words, pretend that your friend is standing still, and that your two choices, rather than running in one direction or the other, are to stand still as well, or to go towards your friend (at 2x the speed that you can actually run): after all, these are the two possibilities in the original problem: that you, at any point in time, are maintaining a constant distance from your friend (if you’re going the same direction), or that you are moving towards your friend at 2x the speed that you can run — thus the setup is equivalent.

So we can think of it this way: your friend is standing still. You, over the course of 30 minutes, can press a button as many times as you want, and each time you press the button, you switch between 2 possible modes, in mode 1 you stand still, and in mode 2 you move at 2x speed towards your friend – obviously, if you could, you’d stay in mode 2, but the trick is that you never know which mode you’re actually in. Suppose you decide to spend X minutes in one mode and Y minutes in the other — i.e. the amount of time between even button pushes and odd ones is X minutes, and the amount of time between odd button pushes and even ones is Y minutes (so X+Y = 30). Then, if it turns out you spent X minutes in mode 1, you will cover X*2*s (where s is your speed) + Y*0 = 2sX miles after the 30 minutes expire. If it turns out you spent  minutes in mode 2, you will cover 2sY miles after the 30 minutes expire (assume speed s is expressed in miles/minute). So, given that you don’t know which mode is which, the expected distance you’ll cover is:

(1/2)*(2sX) + (1/2)*(2sY) = s(X+Y)

And, if you cover this distance, and if the total track distance is sZ (i.e. if it takes Z minutes to run the full track), then the probability of a meeting is s(X+Y)/(sZ) = (X+Y)/Z

So, for example, if the track takes a total of 90 minutes to run, the probability of a meeting is 1/3. It doesn’t matter how many minutes you spend going in one direction or the other. You can change directions a much as you want.

Wait one minute though! There is an assumption I glossed over: that is that you don’t cover more than the entire loop in 30 minutes during either the X minutes in one mode or the Y in the other mode. If you cover the entire loop, the probability of a meeting is 1, not greater than 1 (probabilities never exceed 1!). Thus, in the formula, I should have used min(2sX,sZ) and min(2sY,sZ) in place of 2sX and 2sY, respectively. Then it becomes:

probability of meeting = 1/2*(min(2sX,sZ) + min(2sY,sZ)) / sZ = (min(X,0.5Z)+min(Y,0.5Z))/Z

So, any amount by which either X or Y exceeds 0.5Z is wasted time, and you must change directions.

Thus: the final answer is that it doesn’t matter how many times you change directions over the course of the run, as long as you guarantee that the cumulative time spent in either direction does not exceed half the time it would take to run the full loop. If you follow these instructions, the probability of a meeting is equal to 30/Z, where Z is the amount of time it takes to run the full loop.

Solution to the more complicated version will come later (unless a commenter gets it first).