This week the #puzzle is: How Far Can You Run Before Sundown? #maximum #strategy #recursion

You’re participating in a trail run that ends at sundown at 7 p.m. There are four loops: 1 mile, 3 miles, 3.5 miles, and 4.5 miles. After completing any given loop, you are randomly assigned another loop to run—this next loop could be the same as the previous one you just ran, or it could be one of the other three. Being assigned your next loop doesn’t take a meaningful amount of time; assume all your time is spent running.

Your “score” in the race is the total distance you run among all completed loops you are assigned. If you’re still out on a loop at 7 p.m., any completed distance on that loop does not count toward your score!

It is now 5:55 p.m. and you have just completed a loop. So far, you’ve been running 10-minute miles the whole way. You’ll maintain that pace until 7 p.m.

On average, what score can you expect to earn between 5:55 p.m. and 7 p.m.?

And for extra credit:

Now let’s add one more wrinkle. At some point during the race, if you’re unhappy with the loop you’ve just been randomly assigned, you’re granted a “mulligan,” allowing you to get another random assignment. (Note that there’s a 25 percent chance you’ll be assigned the same loop again.) You don’t have to use your mulligan, but you can’t use it more than once.

As before, the time is 5:55 p.m. You have just completed a loop, and you haven’t used your mulligan yet.

With an optimal strategy (i.e., using the mulligan at the right moment, if at all), on average, what score can you expect to earn between 5:55 p.m. and 7 p.m.?

How Far Can You Run Before Sundown?

Intermission:

So. I didn’t get the extra credit last week. No shame in that. I had all the points from the previous puzzles of Q3. We were a group of 10 persons able to say that. I am now in the group of 6 persons, who dropped out from that max points group, now counting 4 members.

Still. It made me wonder. What was required to solve the extra credit? How does one find a strategy?

• Make a list of all the strategies you can think of. Remember to include the optimal one. 😉
• Test every item on the list.
• Declare a winner.

This requires good brainstorming skills. Also in this case I couldn’t leap this hurdle:

• A strategy is a list of “given voucher situation A, choose bet option B”.

As it turned out, the strategy also needed to include “is this the 1st bet, yes or no”.

Because I actually had the pieces. I had the $55 strategy for the 1st bet. And I had the $35 strategy for having all vouchers. I could just have combined them to get the correct extra credit result.

Ah well.

Highlight to reveal (possibly incorrect) solution:

Program

Information:

• 4 kinds of loops: 1, 3, 3.5 and 4.5 miles.
• Each loop is randomly assigned.
• The time is 5.55 p.m.
• The run ends at 7.00 p.m.
• Speed: 6 mph. (1 mile = 10 minutes.)
• The score equals the number of miles run.
• A loop not finished when the run ends doesn’t count towards the score.
• Question: What will the expected score be for the remainder of the run?

My solution:

• This could probably be done by hand (as I actually ended up doing below), but I wrote a recursive program.
• Begin with the 65 remaining minutes.
• Go through each option / each of the 4 loops that might be assigned.
  • If there’s time enough for a given loop, add this loop to the score and then go through each option again for the remaining time.
  • Stop when time runs out.
• Going backwards through the options, calculate the average of what happened given the 4 options.
• Finally the average for 65 minutes represents the average score.

Example:

• The program has been running for some time. I am looking at the situation with 30 minutes left.
• Going through the 4 options:
  • Option 1, 1 mile, 10 minutes. Note 1 mile and keep looking at the remaining 20 minutes.
    • Option 1, 1 mile, 10 minutes. Note 1 mile and keep looking at the remaining 10 minutes.
      • Option 1, 1 mile, 10 minutes. Note 1 mile and stop.
      • Option 2, 3 miles. Note 0 miles and stop. (Not time enough to run those 3 miles.)
      • Option 3, 3.5 miles. Note 0 miles and stop.
      • Option 4, 4.5 miles. Note 0 miles and stop.
      • The average for the 4 options is 1/4 miles = 0.25 miles.
    • Option 2, 3 miles. Note 0 miles and stop.
    • Option 3, 3.5 miles. Note 0 miles and stop.
    • Option 4, 4.5 miles. Note 0 miles and stop.
    • The average for the 4 options is (1 + 0.25)/4 miles = 0.3125 miles.
  • Option 2, 3 miles. Note 3 miles and stop.
  • Option 2, 3.5 miles. Note 0 miles and stop.
  • Option 4, 4.5 miles. Note 0 miles and stop.
  • The average for the 4 options is ((1 + 0.3125) + 3) / 4 = 1.078125 miles.

Result: Miles added to score, 4.866.

And for extra credit:

Mindomo Program Image

Information:

• Same as above, plus:
• A mulligan can be invoked once during the run and a new random loop be assigned.
• This leads to an optimal strategy.
• Question: What will the expected score be for the remainder of the run, using this strategy?

My solution. The strategy will look like this:

• Given that there’s A minutes left of the run, and a loop requiring B minutes got assigned, and that the mulligan hasn’t been used, should it be used now, yes or no?
• This can be written in a table with all the combinations of A and B.
• Some of the combinations are very easy. If running this loop means there will be 0 minutes left, keep it, we hit the max possible. If running this loop means the loop won’t be finished before the deadline and a better option exists, use the mulligan.
• In general: If the average score over all 4 loop options without a mulligan is C, and keeping the assigned loop on average adds D to the score, and D < C, use the mulligan.

My table:

\ loop time
time left \	45	35	30	10
5	keep	keep	keep	keep
10	mull	mull	mull	keep
15	mull	mull	mull	keep
20	mull	mull	mull	keep
25	mull	mull	mull	keep
30	mull	mull	keep	keep
35	mull	keep	keep	mull
45	keep	keep	mull	mull
55	keep	mull	mull	keep
65	keep	keep	keep	keep

Let me go through an example, related to the image. (Might contain errors as I later changed the algorithm a little.)

• When there’s 10 minutes left (yellow), from left to right the 4 options (in minutes 45, 35, 30, 10, green) add nothing (-0), nothing, nothing and 10 (*) to the score (calculated in minutes). Furthermore, the first 3 options left no time. The 4th option uses all the time left. Therefore the first 3 options are good for a mulligan, while the 4th is a keeper.
• Mulligan = happy smiley, yes, please use the mulligan.
• Keeper = green flag, you have reached a good option.
• (*) From the yellow to the right most option below, there’s a difference from 10 to 0. This is because the route was through a 10 minute loop. Reaching the green flag, there’s no time left and nothing further added to the score.
• The 4 possible options from the yellow state adds 0, 0, 0 and 10 to the score. This is 10/4 = 2.5 in average.
• Another way to say the green flag is a keeper, is because 2.5 < 10.
• When there’s 20 minutes left (orange), similar construction.
• The 4 possible options from the orange state adds 0, 0, 0 and 10 + 2.5 to the score. Therefore the 3 cyan options are good for a mulligan, while the yellow option is a keeper (purple).
• When there’s 65 minutes left, 1 of the options (orange) will add 45 + 3.13 to the score. As this is less than the average for all 4 options, 48.66, this option is good for a mulligan (red).

I change my program. First I calculate all averages without the mulligan. Then I calculate new averages for the situation with a mulligan. Every time I use a mulligan I drop down to the mulligan free version of the averages. I also fill in a table showing whether I use a mulligan in a given situation.

The result appears to be 5.352 miles.

Just for fun I also implemented a monte carlo program, covering all situations with 0-10 mulligans, assuming the mulligan table is the same all the way up.

Expected score with  0 mulligans: 48.677
Expected score with  1 mulligans: 53.514
Expected score with  2 mulligans: 56.563
Expected score with  3 mulligans: 58.585
Expected score with  4 mulligans: 59.967
Expected score with  5 mulligans: 60.997
Expected score with  6 mulligans: 61.748
Expected score with  7 mulligans: 62.318
Expected score with  8 mulligans: 62.773
Expected score with  9 mulligans: 63.123
Expected score with 10 mulligans: 63.391

It confirms both my results.