1
$\begingroup$

Consider the following problem. A jeep can carry a maximum load of fuel of 1 gallon, and it travels $l$ miles with $l$ gallons of fuel. The jeep moves along a straight line, and is required to cross a desert $x$ miles wide in the most economic way, that is minimizing the required fuel. Let us say that $x > 0$ is the abscissa of the starting point, and $0$ that of the ending point. At $x$ there is a fuel station, where the jeep can load the fuel. Let $N$ be a given positive integer and suppose that at any of the points

\begin{equation} x_1 = \frac{x}{N}, x_2 = 2 \frac{x}{N}, \dots, x_{N-1}= \frac{N-1}{N} x, \end{equation}

there is a dumping station, where in any trip the jeep can dump part of its fuel in order to load it in a future trip. What is the minimum quantity of fuel $g(x,N)$ needed to cross the desert? Clearly, if $x \leq 1$, then only one trip is required and $g(x,N)=x$, but for $x > 1$, the problem is not trivial.

We can easily give a recursive solution to the problem as follows. First of all, let us note that if $P$ is a feasible plan of trips which allows the jeep to arrive at $0$, then we can find another feasible plan $P'$ which arrives at $0$ such that $P'$ is made up a number of trips among $x=x_N$ and $x_{N-1}$, followed by a number of trips among $x_{N-1}$ and $x_{N-2}$, and so on, up to a number of trips among $x_1$ and $x_0=0$. Indeed, assume that the jeep makes $m$ round trips starting at $x$, followed by a last one-way trip $A_{m+1}$ from $x$ to $x_{N-1}$. The i-th of these round trips is made up of the one-way trip $A_i$ from $x$ to $x_{N-1}$, followed by a round trip $B_i$ starting and ending at $x_{N-1}$, and by a one-way trip $C_i$ from $x_{N-1}$ to $x$. Let $g_i$ be the fuel of the jeep when it starts the trip $A_i$. Suppose we replace the sequence of trips $A_1$, $B_1$, $C_1$, ..., $A_m$, $B_m$, $C_m$, $A_{m+1}$ with the sequence $A_1$, $C_1$, ..., $A_m$, $C_m$, $A_{m+1}$ and deposit the quantity $g_i - 2(x - x_{N-1})$ at $x_{N- 1}$ in $A_i$, $i=1,\dots,m$, and $g_{m+1} - (x - x_{N-1})$ at $x_{N-1}$ in $A_{m+1}$. Then we are now in a position to make the trips $B_1$, $B_2$, ... , $B_m$. When we do this the final configuration is not altered. By induction, we can so get the desired $P'$. We call a plane like $P'$ a standard plan.

Now, if $S$ is a standard plan which realizes the optimal solution, then clearly the plan $S_n$, $n=1,\dots,N-1$ obtained from $S$ deleting the trips starting at $x_m$, for $m > n$, realizes the optimal solution g(x_n, n). So, if $k_n$ is the number of trips in $S$ between $x_{n-1}$ and $x_n$, we have \begin{equation} g(x_n,n) - g(x_{n-1},n-1) = (2 k_n - 1) \Delta, \end{equation} where $\Delta=x/N$. Moreover, since in the first $k_n - 1$ round trips the maximum fuel that can be deposited at $x_n$ is $1-2 \Delta$, while in the $k_n$-th trip is $1- \Delta$, we must have \begin{equation} (k_n - 1)(1 - 2 \Delta) + 1 - \Delta \geq g(x_{n-1},n-1). \end{equation} Now note that, since we want to minimize the consumed fuel, clearly $k_n$ is determined as the least positive integer satisfying the above inequality. This solves the problem recursively.

The point is to know the behavior of $g(x,N)$ for $x$ and $N$ large. More precisely, we are interested in studying the behavior of $g(x,N(x))$ for $x \rightarrow \infty$, when $N(x)$ is such that $x^2 / N(x) \rightarrow 0$ (see the post The Jeep Problem and Nash's Friends).

Thank you very much for your attention.

PS This problem was studied by Ivan Niven first in 1945, as Fine says in Fine, The Jeep Problem, Americ. Math. Monthly, Vol. 54 (1947), 24-31.

$\endgroup$
  • $\begingroup$ I came across this problem before, but in a slightly different setting. It was a camel that ate bananas as he walked, and he could carry bananas, but he was mentally challenged and would only dump bananas at integer kilometer marks. That time it was a programming puzzle where you would be given how fast he eats bananas, how many bananas he starts with, how many he can carry at once, and how long the desert was as input and your program was supposed to output how many bananas he could maximally end up with. Since it was a programming puzzle, I didn't analyze the mathematical side too thuroughly $\endgroup$ – Arthur Jul 25 '16 at 10:56
  • 1
    $\begingroup$ @Arthur: See math.stackexchange.com/questions/53526. $\endgroup$ – joriki Jul 25 '16 at 15:04
  • $\begingroup$ @Arthur: I notice that the solution to the Camel Problem is recursive too. Thinking about the problem I proposed, I am quite convinced now that no simple closed formula exists for $g(x,N)$. Anyhow I am also convinced that we should be able to give an upper bound for $g(x,N)$ which should allow us to prove the statement in the post math.stackexchange.com/questions/1869729/… $\endgroup$ – Maurizio Barbato Jul 25 '16 at 16:33
  • $\begingroup$ Finally, I found the solution: see the post math.stackexchange.com/questions/1869729/… $\endgroup$ – Maurizio Barbato Jul 29 '16 at 17:13

Your Answer

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

Browse other questions tagged or ask your own question.