Suppose a car's fuel tank can carry at most 500 unit fuel, but it need to travel from A to B where the distance between them is 1000 km. Suppose that the fuel consumption rate is 1 unit/km, and between A and B, the car can store any amount of fuel at any point. The question is, what is the minimum unit of fuel needed at the starting point A?

To make the problem clearer, consider a simple problem of traveling 5 km, with the car's max fuel 4 unit. Of course, if you just take 4 unit fuel at the starting point, it cannot finish 5km. So you can pick a position, say 1 km from the start, when your full fueled car reach here, you have 3 unit left, so you store 1 unit here and then go back to start with 4 unit again. This time, when you reach this point, you have 3 unit left because you traveled 1km, but you can take 1 unit from your previous storage to make your fuel tank full again. And now you have 4 unit fuel with your distance to destination 4km, so you can finish your journey smoothly.

For the original problem, assume that I can only store the fuel at integral km distance from the start, I obtain the solution that I need 3848 unit at the start, and I will store the fuel at 24 km, 62 km, 107 km, 163 km, 234 km, 334 km and 500 km such that when I reach 500 km, I can guarantee that I have 500 unit for the rest of the journey. But in the original problem, there is no such limit which means that you can store at, for example, 24.675 km if only it can reduce the total fuel needed. So how can we obtain the optimal solution for this?

  • 1
    $\begingroup$ Closely related to, if not a duplicate of, math.stackexchange.com/questions/97419/travelling-with-a-car. See also the Jeep problem $\endgroup$ – Marc van Leeuwen Nov 19 '12 at 13:28
  • $\begingroup$ @Marc van Leeuwen: Yes it is some what related but not exactly the same. $\endgroup$ – AmFCG Nov 19 '12 at 14:07
  • $\begingroup$ Isn't this exactly the jeep problem Marc linked to? $\endgroup$ – Rahul Nov 19 '12 at 18:58
  • $\begingroup$ Can you please explain the strategy to get 24, 62, 107, 163, 234, 334 and 500 kms? I couldn't able to get it. $\endgroup$ – Kernelf Aug 9 '17 at 17:48
  • $\begingroup$ I got my strategy using discrete DP (dynamic programming) algorithm $\endgroup$ – AmFCG Jan 31 '18 at 10:25

Wouldn't it be more optimal to store $\frac{500}3$ units at $\frac{500}3$ km, go back. Now your fuel budget is $500\cdot (1 + 1/3)$, so store $500\cdot \frac{1 + \frac 13}3$ units at $500\cdot \frac{1 + 1/3}3$ km, go back. Now your fuel supply is $500\cdot (1 + (1 + \frac 13)\cdot \frac 13)$, so store $500\cdot (1 + (1 + \frac 13)\cdot \frac 13)$ etc...it's a series you need to get to 2.


$\frac 13 + 1 = \frac{1+3}3$

$\frac{4/3}3 + 1 = \frac{1+3+9}9$

$\frac{10/9}3 + 1 = \frac{1+3+9+27}{27}$

etc. When does $(3^0 + 3^1 + 3^2 + 3^3 +\cdots + 3^n)/3^n$ reach 2?

  • $\begingroup$ Sorry, your answer is not correct because $1/3^n\cdot\sum_{i=0}^n3^i=3/2-3^{-n}/2$, so it will never reach 2. $\endgroup$ – AmFCG Nov 19 '12 at 14:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.