I've been following the discussion of this problem. Don't like the stage by stage solution. I've been trying to develope a general solution, but failed. Now, I think the current stage by stage solution (by fzy and Warren) may be the best we can do. I have a minor problem with the stage though. It seems that no matter what, the first storage spot has to be at the half point (i.e. 500 km). At the begining, when you first drive out with 2 barrels (one in the tank of the car, one in the barrel), there's no other place to store the barrel other than the 500 km place (can't be longer or shorter). However, none of your solutions mention the 1/2 point storage place. May be I didn't read it careful enough. I think the best thing to do is to write out the exact procedure of doing the barrel problem.

I did not like the way either, and that is why I waited for so long in the hope of some one can provide a better answer first. But if our solution is indeed the best, the only way to reach it is iteration, because each number depends on the ones before it.

Also in my solution, the 1/2 point plays an important role in calculating the numbers. The whole problem may be reduced to how to reach the 1/2 point (and beyond) in the most efficient way. The way you described (called the all-out way in my earlier post) did not take advantage of storing some fuel in the middle, and most likely will not be optimal. In fact, it uses about 1/2 of the total fuel to reach the 1/2 point. For our way, it is about 43%. So any method that can reach the 1/2 point using less than 43% wil be better than ours. But it cannot be by a lot. It is mathematically not possible to use less than about 40%:

With 2N barrels of fuel, you need 2N-1 trips to carry them anywhere. So it suggests the differential equation of dy/dx = y - 1, where y is fuel consumption and x distance. Solve it and we have y = exp(x) +1. Now we see that y(x - 1/2) is about 60% of y(x).