Update Sept 3: Solution (to original version) is here
Update 7/31: The solution to this puzzle requires not much math at all, if you think about it the right way. I’m tempted to only award beer if someone gets the more complex version (at the end of post–that one also requires only minimal math), but I’ll stick to my word instead.
——————————————————————
I went running in the park today, and thought of the following puzzle: suppose you are going running in the park, and that there is one loop-shaped running path which you will run along for a total of 30 minutes. You have a friend who will be running along the loop for exactly the same 30 minutes as you (i.e. you start and end at the same time), and at exactly the same speed as you.
You have no idea where your friend will start his or her run along the loop, nor do you know what direction your friend will run in (clockwise our counterclockwise) but you do know that your friend will run in a single direction for the entire 30 minutes.
You want to maximize the probability that you will run into your friend while running. All that you have control over is which direction you are running in at any point in time along your run. So one possibile course of action is to run in one direction for the entire 30 minutes (either clockwise or counter). Another is to run in one direction for a certain period of time, and then (assuming you haven’t met) switch directions and finish the run in the other direction. Or you can switch directions multiple times, each after specified period of time.
So, what is the optimal course of action in order to maximize the probability of meeting? If there are multiple courses of action that give the equivalent, maximal, probability, what are they? The answer may depend on how much of the loop you cover in 30 minutes (but assume that you cover less than half the full loop–otherwise you can clearly guarantee a meeting)*. Assume that you are very nearsighted, so you only see your friend when you are actually crossing paths. And remember that you and your friend travel at the same speed, and you have no control over, or knowledge of, where you start in relation to your friend, or the direction of his/her run.
I will buy, for the first person who can solve this puzzle (i.e. give an answer and prove it), 2 beers at a bar.
For those of you who don’t like getting too deep into the weeds with puzzles like this: can you make any statements generally about the strategy you should employ (no beer awarded for such statements)?
More complex version: Modify the puzzle by specifying that you and your friend don’t travel at the same speed, but rather that the ratio of your speed to your friend’s speed is X.
*edited 7/31. if solution is provided based on original language, it’s ok as far as the beer award is concerned.
You should run back and forth, changing directions as close to constantly as possible. This means you’ll be effectively staying in the same small spot for 30 minutes. Since your friend will cover the entire loop in that time, he is guaranteed to run into you. This works regardless of what speed either of you are traveling, though for the more complex version it may require longer than 30 minutes if your friend is slow.
Andrew – what about cases where your friend can’t run the full loop in 30 minutes?
(This is in response to the simpler version in which the two running speeds are equal. I’ll attempt the more complex version later.) It seems to me that you can’t do better than simply running in one direction for the whole 30 minutes. Here is my attempt at proof. Call f the fraction of the loop that your friend covers in 30 minutes. That means that if you simply stand on the track (or change directions very frequently as Andrew suggests) you have a probability f of crossing paths with your friend. Now _if_ you start out running in opposite directions (which you don’t know) than you each will cover f of the track so your probability of crossing is 2f. There is a probability of ½ that you start out running in opposite directions. If, however, you start out running in the same direction then the probability that you cross is zero. So the total probability that you cross if you run continuously in one direction given your ignorance of your friends direction is (1/2)2f + (1/2) 0 = f. Anytime you change directions you increase the likelihood of crossing your friend if you are initially going in the same direction, but extinguish the likelihood if you are initially going in the opposite direction. No matter when or how often you change directions, your probability of crossing will be f. So changing directions doesn’t matter and you can just keep running in the same direction.
Let me try another very angle at a loose proof. (If you’re looking for rigor, I’m out.) Imagine spinning the entire track under the runners in the same speed and opposite direction of your friend’s running. That way, your friend stands still as he runs on a conveyor belt. You run at twice the speed when running in the opposite direction but stand still when you run in the same direction as your friend, but you don’t know which is which. I hope that makes it more clear that changing directions in this case doesn’t affect the probability that you will meet. It seems that this should be generalizable to the complex case in which the running speeds are unequal. The conveyor belt thought experiment would simply make it so that your speeds in the two directions are unequal, but you still don’t know which direction is which. You probably want me to derive something in terms of X, but it seems clear that the probability of crossing will be the average of the probabilities of running in one direction and that of running in the other, and since you don’t know which is which there is no benefit in changing direction.
Albert,
Interesting ideas. The conveyor belt idea is exactly what I meant when I referred to thinking about this in “the right way” (although I didn’t actually think of a physical conveyor belt, but that certainly makes it more explicit).
One question though (first I’ll address your answer to the simpler version):
-In the simpler version, would you say that, no matter how much of the track you can cover in 30 minutes (up to a maximum of the entire track), whether your change directions or not is irrelevant to the probability of meeting?
Ah. Very interesting. I see. My solution applies only if the fraction of the track covered in 30 minutes is < 1/2.
If you can cover the entire track in 30 minutes then Andrew is right. Standing still (i.e. changing direction very frequently) gives you certainty that you will meet your friend. If you can cover more than 1/2 the track in 30 minutes but less than all of it, you should turn around after you've covered 1/2 the track. The reason is that after you've run half the track you can be certain that you are running in the same direction as your friend since s/he has covered 1/2 the track too and if you were running in opposite directions you would have met.
Nice puzzle!
That changes things for the more general case which I'll have to reconsider.
The problem indicated that the loop is more than 30 minutes long. If the loop is greater than 60 minutes long, but less than 120 minutes long, pick a direction and run in that direction for 30 minutes. If the loop is less than 60 minutes long, or 120 minutes long or more, do as your conscience prompts (if the choices are between resting and running at the same speed as your friend). The proof is below.
Spread the loop out to a line and imagine you are standing at the center of it — the two endpoints of the line are actually the same point — the one furthest away from you on the loop.
Assume without loss of generality that your friend is on the left-hand segment, running towards you or away from you (he has a 50% probability of being on each of the two segments, running towards you or away from you in each case, also with 50% probability).
If the distance to the endpoint is less than 30 minutes, might as well stay where you are (joke). You have a 50% chance of his running towards you. If you start running, your probabilities are as follows: (i) you choose to run to the left, in which case you will meet your friend if he is running towards you (25% probability); (ii) you choose to run right, in which case you will meet your friend if he is running away from you (25% probability); total probability of meeting your friend if you start running is also 50%, so rest.
If your distance to the endpoint is more than 30 minutes, but less than 60 minutes, start running. If you run in the correct direction (left if he’s going towards you; right, if he’s going away from you); you will meet; as before, you have a 50% probability of meeting him. If you stand still, you have a 25% chance of his meeting you.
If your distance to the endpoint is a number – call it d – that is more than 60 minutes, then parse it out as follows, assuming that his starting point is uniformly probable along the loop.
With probability p=60/d * 50% he is running towards you, and is less than 60 minutes away, in which case if you start running you have a 50% probability of choosing the correct direction and hence meeting him. With a probability of (1-p)*50% he is running towards you and is more than 60 minutes away, in which case you will not meet whether or not you choose the correct direction. With a probability of 50% he is running away from you, in which case you will not meet. So the overall probability of meeting him if you start running is 25% * 60/d. If you stand still, then the probability of his reaching you is his probability of running towards you (50%) times the probability of his being less than 30 minutes away (30/d), or 50%*30/d.
Changing direction while you run is identical to running in your terminal net direction – the direction in which you end up in relation to your origin — at a slower speed, which does not affect your probability of meeting if the d is less than 30 minutes or greater than 60 minutes, but reduces it between d=30 and d=60.
Simina – suppose the loop is 45 minutes long. What is the probability of meeting your friend if you choose the optimal strategy?
oops — I think it’s 66%.
I mean 2/3
and you stand still.
Using L as the length of the loop, if L > 60, I think the probability if you stand still is 30/L.
I am coming up with:
1) if the loop is between 45 and 60, the probability is 50%;
2) if it is over 60, the probability is 30/L.
3) If it is 45 or less but more than 30, it is 1-15/L, but if it is 30 or less it is 1.
I also think it doesn’t matter what you do, so you might as well stand still.
I also think I’ve spent a lot of time on this problem.
hmm. It seems odd that if the length is 31 minutes, the probability is 0.516, but if the length is 30 minutes, the probability is 1.
And don’t worry, I spent a good portion of my run thinking about it, as well as a decent amount of time afterwards, and there wasn’t even a potential beer reward for me to look forward to.
Your best chance is to run in place regardless of the length, given the length is beyond the distance you can cover in 30 minutes.
MAT – does this answer apply to the more complex version as well?
And, in the simple version, if the path takes a total of 2 hours to cover, is your method better than running in 1 direction the whole time?
I’m not going to try to solve this. I just was contemplating it and felt obliged to point out that it is far from a useless theoretical question. Any bright young man who has noticed that his regular jogging time and place overlaps with that of a particularly beautiful young woman will have given a fair amount of thought to heuristics for rough solutions to the general case of this problem.
Run in one direction for 30 minutes without changing direction. This will place you as far from where you parked your car as possible, so if you don’t meet your friend then when you turn around and walk exhausted back to your car you will have a high chane of meeting him walking to his or flirting with some cute co-ed or laid out on the side of the path with a sprained ankle.
Just to be clear, where’s the randomness here? Is it in the friends starting point and direction?
Ari – Yes.
Just run and hope. If you don’t meet, well, i guess that was just meant to be.
Run 15 min clockwise, then turn around and run 15 minutes counterclockwise.
You will meet if friend is running counterclockwise and starts out within 30 minutes distance of you, and if friend is running clockwise and starts out within 30 minutes of you.
If it is a 30 minute loop, your chances are 100%.
For more than 30 minutes, it is 30/L.
Pingback: Answer to Running Puzzle | Questions about Politics, Philosophy, and Math