How Many Miles to Retrieve an Object N Miles into a Desert?

Question

The problem:

Suppose that you are interested in retrieving an object located in the middle of the desert, n kilometers away. Your car can carry enough fuel to travel 3 kilometers, and you have an unlimited supply of spare fuel tanks which you can use to leave deposits of fuel throughout the desert. Your starting point has as much fuel as you want. What is the minimal number of miles it is possible to travel in order to retrieve the item?

This isn't homework, this is review from a class I took a while back. The solution mentions moving a tanker of gas a distance $\epsilon$, meaning that it would have $3-2\epsilon$ gallons in it. It goes on to say that this would require only $(1-\frac{2}{3}\epsilon)^{-n/\epsilon}$ kilometers, which in a limit gives an exponential, but that also would involve depositing a bit of gas at the end. (Which would be wasteful)

So my question is two fold, where did the above solution come from, and what is an even better answer, that doesn't leave gas at the end?

Edit: There is a solution given here, but I don't find it to be a good argument of correctness. I realized there is a limiting behavior here that results in the exponential, but I'm still not sure why it's the correct answer.

https://inst.eecs.berkeley.edu/~cs70/fa13/disc/sol1.pdf

Answer 1

Consider, at each point in the desert, the number of times you go through that point. I think you will convince yourself that the further away you are in the desert, the less tims you are going to ride through (riding far away is more costly).

Furthermore, the order in which we make the trips does not matter as long as the fuel is there, so we can suppose the strategy looks like this :

There is an integer $n$ ; distances $0=d_0, d_1, d_2, \ldots d_n = N$ ; and fuel quantities $f_0,f_1,f_2, \ldots f_{n-1},f_n = 0$.
Then we define for each $1 \le i \le n$, the strategy $S_i$ to, from $d_i$ and using $f_i$ fuel, reach $N$ and go back to $d_i$ :
The strategy $S_i$ is to use $f_i$ fuel at $d_i$ to bring $f_{i+1}-(d_{i+1}-d_i)$ fuel to $d_{i+1}$ in $n-i$ trips, then do $S_{i+1}$, and finally go back using the $d_{i+1}$ fuel left.

Since we want to do $n-i$ trips from $d_i$, it is useless to have more than $3(n-i)$ fuel at that point, so $f_i \le 3(n-i)$.

Furthermore, suppose that $f_i < 3(n-i)$ for $0 < i < n$. Then if we reduce $d_i$ by $\epsilon$, we can bring $2(n+1)\epsilon$ more fuel to $d_i$, while using $2n\epsilon$ more fuel to bring it to $d_{i+1}$ which is a net gain. Therefore, it is always the best choice to choose $d_i$ such that $f_i = 3(n-i)$ for $0 < i \le n$.

Now in order for $S_i$ to work without waste we must have $f_i - f_{i+1} = 2(n-i)(d_{i+1}-d_i)$. This gives us enough equations to relate $f_0$ and $N$ :

$d_{i+1} - d_i = 3/2(n-i)$ for $i > 0$, and $f_0 = 3n-3+2nd_1$, which gives
$N - d_1 = \frac 32 \sum_{k=1}^{n-1} \frac 1k$ and $f_0 = 3n-3+2n(N - \frac 32\sum_{k=1}^{n-1} \frac 1 k)$

Since $3n-3 \le f_0 \le 3n$ we get $0 \le d_1 \le 3/2n$ so that this strategy gives $\frac 32 \sum_{k=1}^{n-1} \frac 1k \le N \le \frac 32 \sum_{k=1}^n \frac 1k$, with $df_0/dN = 2n$

Putting the strategies for various $n$ together, the resulting function $F(N) = f_0(N)$ (needed fuel in terms of distance), is piecewise affine, with each piece having slope $2n$ and length $3/2n$

So $F(0) = 0, F(3/2) = 3, F(9/4) = 6, F(11/4) = 9, F(25/8) = 12 \ldots$

Since $\sum_{k=1}^n \frac 1k = \log n + O(1)$ we have $F(3\log n/2 + O(1)) = 3n$, which shows that the fuel needed is an exponential function of the distance.

Answer 2

Silly solution: Carry $\frac{2n}{3}$ gas tanks in/on your car, and you will be fine. :) This is because the problem doesn't specify the carrying capacity of your car. I choose mine to be a gas transport truck. :D