4

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.

athin
  • 34,177
  • 4
  • 70
  • 221
JimSi
  • 309
  • 1
  • 8
  • 2
    https://puzzling.stackexchange.com/questions/230/a-camel-transporting-bananas could be related even though i dont understand the question. – Oray May 03 '18 at 08:26
  • 1
    @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. – JimSi May 03 '18 at 08:31
  • You cannot get to 1.5 from .2 with a 1 tank – paparazzo May 03 '18 at 09:00
  • @paparazzo You can, but you need to deposite 0.4 unit of fuel at 0.5 unit of distance, and come back to take the 0.9 fuel left at 0.2 distance – Saeïdryl May 03 '18 at 09:06
  • i am pretty sure that this type of question is asked before, cant find it. – Oray May 03 '18 at 10:10
  • https://puzzling.stackexchange.com/questions/17156/how-much-water-do-you-need-to-cross-the-desert this is it i guess – Oray May 03 '18 at 10:13
  • @Oray, I still don't get how this is the camel problem, then what is the answer, the camel problem gives 3 when I can give an example of 2.9?? – JimSi May 03 '18 at 11:16
  • How does this differ from the classic definition of the Jeep problem, as explained at https://en.wikipedia.org/wiki/Jeep_problem (the 'crossing the desert' variant)? – jsm May 03 '18 at 11:49
  • 1
    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. – athin May 03 '18 at 12:04
  • @jsm, so what is the answer then, 3? – JimSi May 03 '18 at 12:09
  • @athin, don't see how it is wrong – JimSi May 03 '18 at 12:17
  • @JimSi On your third trip, at distance 0.2, you have a 0.7 unit from the station and you have put a 1.2 fuel in your cache. Your filling tank won't be enough to take that 1.9 fuel! – Untitpoi May 03 '18 at 12:22
  • 1
    @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. https://ibb.co/kxCwm7 – JimSi May 03 '18 at 12:32
  • 1
    @JimSi you're right, you should add that in your question! I guess it could be optmized though. – Untitpoi May 03 '18 at 12:40
  • @athin, see my drawing. – JimSi May 03 '18 at 12:58
  • yep2 saw that, nicely done! :D – athin May 03 '18 at 13:04
  • If you are going to answer then hide it and write it up in text. – paparazzo May 03 '18 at 13:26
  • @JimSi this is not camel problem though it is the same question as water problem :) only difference is yours is 1.5 units, that question is 2 units. – Oray May 03 '18 at 14:31

2 Answers2

5

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$.

athin
  • 34,177
  • 4
  • 70
  • 221
  • 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. – JimSi May 03 '18 at 15:49
  • 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. – athin May 03 '18 at 16:27
0

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

Chronocidal
  • 1,943
  • 9
  • 19
paparazzo
  • 500
  • 5
  • 12