You have 45 carrots, and want to get a donkey to take as many as possible of them to a endpoint 15 miles away. Trouble is, the donkey can only carry 15 carrots at a time, and insists on eating a carrot early in every mile. How many carrots can you get to the endpoint?
The prize was won by Wei-Kong Mao. The answer is 8 carrots.
Solution: If you take 15 carrots, you can get the donkey to go to the first milestone, drop 13 carrots there, and come back to get another 15. (13=15 minus one carrot eaten for the mile out and another carrot for the mile back).
Go to the first milestone again, leave another 13 there, come back again, pick up the last 15, and drop 14 at the first milestone. Now you have 40 at the first milestone.
Then 35 at the second, 30 at the third.
Once you are down to 30 carrots, you can carry the maximum number of carrots further at a loss of only 3 carrots per mile. (One journey out to the next milestone, one back to pick up more, one out again).
So: 27 at the fourth milestone, 24 at the 5th, 21 at the 6th, 18 at the 7th, 15 at the 8th.
Now you can head straight for the endpoint with no more backtracking. The donkey will need 7 carrots for this last stretch, and so you can get 8 to the endpoint.
This is the best solution. There is no penalty in the problem for time lost in backtracking. Any solution getting fewer than the maximum possible number of carrots to each milestone thus differs from the one above only in having a smaller number of carrots at some milestone, and therefore cannot be better.
It can be tweaked a little. You could take 15 to the third milestone, leave 9 there, return, bring another 15, leave another 9, return, bring a final 15 to add 12 (15 minus 3 eaten on the way) to the total at the third milestone. That’s another way of getting 30 to the third milestone, but not very different from doing it mile by mile.