4
$\begingroup$

You have a car that has a tank that can store $1$ unit of fuel. You need to get to a destination $1.5$ units of distance away. The car travels $1$ unit of distance on $1$ unit of fuel. You can deposit fuel along the route, but capacity is never more than $1$ unit. What is the minimum amount of fuel you need to make the trip?

My attempts at a solution: a solution would have the car having $1$ unit of fuel at $0.5$ metres equal. So it is not making any unnecessary returns. So the problem can be reduced to the minimum amount of fuel required to transport $1$ unit of fuel a distance of $0.5$.

I know it should be about $2-2.9$ units. Here is a drawing of using $2.9$ units:

enter image description here

Is there a way to optimize this?

Edit: I cannot see how this is the same as the camel problem, because the camel problem would give an answer of $3$, when $2.9$ is possible.

|improve this question
$\endgroup$
  • 2
    $\begingroup$ puzzling.stackexchange.com/questions/230/… could be related even though i dont understand the question. $\endgroup$ – Oray May 3 '18 at 8:26
  • 1
    $\begingroup$ @Oray I have seen the camel problem, I think it is related, but slightly different (I may have misunderstood), I feel it is an amalgamation of that and the jeep problem, where you have to go back to the base every trip, and the camel problem where you are trying to maximise the amount you bring a set distance. $\endgroup$ – JimSi May 3 '18 at 8:31
  • 1
    $\begingroup$ Your 2.9 is wrong. When you reach distance 0.2, you can only filling your tank up to 1. So your car will stop at distance 1.2. $\endgroup$ – athin May 3 '18 at 12:04
  • 1
    $\begingroup$ @Untitpoi Im not suggesting to fill it all up when at 0.7 and 1.2 cache, I suggest to take 0.3 from the cache, then go to a distance of 0.5, go back and pick up the rest. See this image , I have drawn out, , really do not get it. ibb.co/kxCwm7 $\endgroup$ – JimSi May 3 '18 at 12:32
  • 1
    $\begingroup$ @JimSi you're right, you should add that in your question! I guess it could be optmized though. $\endgroup$ – Untitpoi May 3 '18 at 12:40
5
$\begingroup$

Ok, first of all, this is a classic Jeep Problem but it's inverted: instead of given how many fuel then maximize the distance, we are given the distance and minimize the fuel.

Actually on above link, there is a formula to calculate this:

Given $n + f$ units of fuel (where $0 \le f \lt 1$), the maximum distance will be: $$ \frac{f}{2n+1} + \sum_{i=1}^{n}{\frac{1}{2i-1}}$$

(Honestly, I can't prove that formula tho...)

Continuing on:

Using only $2$ units of fuels ($n = 2$ and $f = 0$) won't reach $1.5$ units of distance since the maximum distance will be: $$ \frac{0}{5} + (\frac{1}{1} + \frac{1}{3}) = 1\frac{1}{3} \approx 1.333$$

Because OP has proven that we can use less than $3$ units of fuels, then:

$n$ must be $2$ and we have to find $f$ such that: $$ \frac{f}{5} + (\frac{1}{1} + \frac{1}{3}) = 1.5$$ Turns out, the $f$ is $\frac{5}{6}$ so we need $2\frac{5}{6} \approx 2.833$ units of fuels in total.

In practice, to prove it's possible:

Suppose we divide $1.5$ units of distance to $4$ points like this.

enter image description here

Then do the following:
- Take $1$ units of fuels on $A$.
- Go to $B$, put $4/6$ units of fuels, go back to $A$.
- Take $1$ units of fuels on $A$.
- Go to $B$, take $1/6$ units of fuels on $B$.
- Go to $C$, put $1/3$ units of fuels, go back to $B$.
- Take $1/6$ units of fuels on $B$, go back to $A$.
- Take $5/6$ units of fuels on $A$.
- Go to $B$, take $2/6$ units of fuels on $B$.
- Go to $C$, take $1/3$ units of fuels on $C$.
- Go to $D$.

|improve this answer
$\endgroup$
  • $\begingroup$ this answered my confusion perfectly, It is deceptively quite tricky and the reverse as you say. I guess deriving the formula would be the last piece. $\endgroup$ – JimSi May 3 '18 at 15:49
  • $\begingroup$ I'm afraid the proof for the formula is "too math" for this puzzling site.. or it isn't? I may give some "greedy" observation but still can't prove it is indeed the optimal atm. $\endgroup$ – athin May 3 '18 at 16:27
0
$\begingroup$

I think 3 tanks

[S][0][0][0][0][0][E]
travel 1/4 and leave 1/2 tank
[S][½][0][0][0][0][E]
travel 1/4 top off then travel 1/4 and leave 1/4
[S][¼][¼][0][0][0][E]
travel 1/4 top off then travel 1/4 and top off the travel 1 to destination

|improve this answer
$\endgroup$
  • $\begingroup$ On the second trip, you could also top up in both directions and leave more fuel at the turn-around point - this would mean 1 less top-up on the third trip $\endgroup$ – Chronocidal May 3 '18 at 12:23
  • $\begingroup$ @Chronocidal I don't follow. Nice edit. $\endgroup$ – paparazzo May 3 '18 at 13:09

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