2

The classical jeep problem is the following. 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, while at any point $y < x$, there is a dumping station where the jeep can dump part of its fuel, in order to load it in a future trip.

The solution in this case was found by Fine, The Jeep Problem, Americ. Math. Monthly, Vol. 54 (1947), 24-31. The minimum required quantity of fuel $f(x)$ is the piecewise linear function having slope $2n+1$ on the interval $\left[ D_n, D_{n+1} \right]$, where $D_0=0$ and \begin{equation} D_n = \sum_{k=1}^{n} \frac{1}{2k-1} \end{equation} for $n > 1$. From this result Fine easily derives the asymptotic formula for $f(x)$: \begin{equation} f(x) = \frac{1}{4} \exp(2x - \gamma) + \mathcal{O}(e^{-2x}), \end{equation} where $\gamma$ is Euler's constant.

Now let $N$ be a positive integer and let $g(x,N)$ be the minimum required fuel to cross the desert when the jeep can dump (and subsequently load) the fuel only at the points

\begin{equation} y_1 = \frac{x}{N}, y_2 = 2 \frac{x}{N}, \dots, y_{N-1}= \frac{N-1}{N} x. \end{equation}

Suppose to choose for every $x \geq 0$ the positive integer $N(x)$ such that $x^2 / N(x) \rightarrow 0$ as $x \rightarrow \infty$. Fine states at the end of his paper without proof that $[g(x,N(x)) - f(x)]/f(x)$ is not larger that $1 / 2$ for large $x$, meaning that \begin{equation} \limsup_{x \rightarrow \infty} \frac{g(x,N(x))-f(x)}{f(x)} \leq \frac{1}{2}. \end{equation} Does anyone know how to prove this result? Thank you very much for your attention.

PS I discovered the Jeep Problem in the book "A Beautiful Mind" by Sylvia Nasar. In chapter 17, she tells a curious story in which Nash was challenged by one of his friends to give an upper bound for the minimum required quantity of fuel. Nasar writes in the book that "there is no optimal solution to the problem, as it turns out". She is not explicit about what version of the jeep problem Nash and his friends were discussing: it seems from her words that it was the version later analyzed by Rote and Zhang, Optimal Logistics for Expeditions: the Jeep Problem with Complete Refilling. In any case, also for this version there is an optimal solution, and this existence property is true for all the versions I know of the jeep problems (see the references in https://en.wikipedia.org/wiki/Jeep_problem and http://mathworld.wolfram.com/JeepProblem.html ), so I think Nasar simply made a wrong statement (maybe she simply meant that an optimal solution was not known at that time, or simply she quoted a wrong statement by someone).

PSS A very short and elegant proof that $f(x)$ is the minimum required quantity of fuel is found in Gale, The Jeep Once More or Jeeper by the Dozen, Americ. Math. Monthly, 77 (1970), 493-501.

Maurizio Barbato
  • 3,638
  • Your statement with the $\limsup$ is not exactly what you wrote with text. What you wrote with text is written mathematically as $\exists x_0, \quad \forall x \ge x_0, \quad g(x) - f(x) \le \frac 12 f(x)$. The statement with the limit superior is slightly weaker because it means that for every $\varepsilon > 0$, the ratio $\frac{g(x)-f(x)}{f(x)}$ is no larger than $1/2 + \varepsilon$ for $x$ large. In some sense, your sentence written in text is the case $\varepsilon = 0$. – Patrick Da Silva Jul 24 '16 at 17:32
  • @Patrick Da Silva: Dear Patrick, I know it's weaker, but I think it is what Fine meant. Anyhow, if you can prove a stronger statement it's better! – Maurizio Barbato Jul 24 '16 at 17:33
  • I am guessing that discretizing the problem should not have a huge effect on the minimum amount of fuel required ; it will raise it a little bit, but the better the discretization (i.e. the larger $N(x)$ is, so that the gaps between stations get smaller), the smaller your upper bound on the $\limsup$ will get. Intuitively that makes a lot of sense, but I am guessing that deriving an actual estimate such as $\frac 12$ just requires to go through the original proof of the minimality of $f(x)$ and take the discrete steps into account. Did you try? – Patrick Da Silva Jul 24 '16 at 17:40
  • One technique would be to use the optimal solution and simply put less gas/distance than possible if the discrete steps were not present. This will not output $g(x)$ but an upper bound for $g(x)$, which can then be used to compute the $\limsup$. – Patrick Da Silva Jul 24 '16 at 17:43
  • @Patrick Da Silva: Dear Patrick, the original problem is not continuous. The jeep can only dump the fuel and load it (if there is any left) in a finite number of points $0 < y_1 < ... < y_n < x$. For sure $n$ can be any nonnegative integer, and the points $y_1, \dots, y_n$ can be arbitrarily chosen (in the original problem): see the wikipedia page. – Maurizio Barbato Jul 24 '16 at 17:59
  • @Patrick Da Silva: Anyhow, without knowing Fine's paper, there is little hope to find a proof of the statement I quoted. – Maurizio Barbato Jul 24 '16 at 18:06
  • I was aware that the problem was not "continuous" to that extent. I meant that if an optimal solution drops fuel at $y$, the "discretized" solution would to be to drop fuel to the closest possible dumping location before reaching $y$. Do you understand what I mean now? – Patrick Da Silva Jul 24 '16 at 18:57
  • @Patrick Da Silva: Yes, Patrick, now I get what you meant! – Maurizio Barbato Jul 24 '16 at 21:11
  • @Patrick Da Silva: What you suggested does' seem a good idea. To see why, consider the case in which $N(x)$ goes like $x^3$. Since the number of points $r(x)$ for the optimal solution increases exponentially with $x$, you have many more points in the latter than for the constrained problem with equally spaced stations. – Maurizio Barbato Jul 25 '16 at 16:38
  • I think anyhow that all the work amounts to find some upper bound for $g(x)$ which allows us to compare it with $f(x)$, given the asymptotic formula for $f(x)$ I wrote down above. – Maurizio Barbato Jul 25 '16 at 16:39

1 Answers1

0

Finally, I found the answer to my question.

First of all, we can easily give a recursive solution to the problem as follows. 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=y_N$ and $y_{N-1}$, followed by a number of trips among $y_{N-1}$ and $y_{N-2}$, and so on, up to a number of trips among $y_1$ and $y_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 $y_{N-1}$. The i-th of these round trips is made up of the one-way trip $A_i$ from $x$ to $y_{N-1}$, followed by a round trip $B_i$ starting and ending at $y_{N-1}$, and by a one-way trip $C_i$ from $y_{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 - y_{N-1})$ at $y_{N- 1}$ in $A_i$, $i=1,\dots,m$, and $g_{m+1} - (x - y_{N-1})$ at $y_{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(y_n, n)$. So, if $k_n$ is the number of trips in $S$ between $y_{n-1}$ and $y_n$, we have \begin{equation} g(y_n,n) - g(y_{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 $y_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(y_{n-1},n-1), \end{equation} or \begin{equation} k_n (1 - 2 \Delta) + 1 + \Delta \geq g(y_{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.

Now, note that if $k_n \geq 2$, then we must have \begin{equation} (k_n - 1)(1 - 2 \Delta) + \Delta < g(y_{n-1},n-1), \end{equation} from which we get \begin{equation} k_n < \frac{g(y_{n-1},n-1) + 1 - 3 \Delta}{1-2 \Delta}, \end{equation} so that \begin{equation} \frac{g(y_n,n) - g(y_{n-1},n-1)}{\Delta} = 2k_n - 1 < \frac{2g(y_{n-1},n-1) + 1 - 4 \Delta}{1-2 \Delta} < \frac{2g(y_{n-1},n-1) + 1}{1-2 \Delta}. \end{equation}

Since we have \begin{equation} g(\Delta \left \lfloor {1/ \Delta} \right \rfloor, \left \lfloor {1/ \Delta} \right \rfloor) = 1, \end{equation} we compare $g(y_n,n)$ with the function \begin{equation} h(y)= c(N) \exp \left( \frac{2y}{1- 2 \Delta} \right) - \frac{1}{2}, \end{equation} where \begin{equation} c(N) = \frac{3}{2 \exp \left( \frac{ 2 \Delta \left \lfloor {1/ \Delta} \right \rfloor}{1 - 2 \Delta} \right) }. \end{equation} The function $h$ is a convex, satisfies the differential equation \begin{equation} h'=\frac{2 h + 1}{1-2 \Delta}, \end{equation} and the initial condition $h(\Delta \left \lfloor {1/ \Delta} \right \rfloor)=1$. From the above inequality for $g(y_n,n)$ we then get by induction that \begin{equation} h(y_n) \geq g(y_n,n), \end{equation} for all $n \geq \left \lfloor {1/ \Delta} \right \rfloor$, so that in particular \begin{equation} g(x,N(x)) \leq c(N(x)) \exp \left( \frac{2x}{1- 2 \Delta} \right) - \frac{1}{2}. \end{equation} Now note that since $x^2 / N(x) \rightarrow 0$ as $x \rightarrow \infty$, we have $\Delta \rightarrow 0$ and $\Delta \left \lfloor {1/ \Delta} \right \rfloor \rightarrow 1$. Moreover we have \begin{equation} \lim_{x \rightarrow \infty} \frac{\exp \left( \frac{2x}{1 - 2 \Delta} \right)}{e^{2x}} = \lim_{x \rightarrow \infty} \exp \left(\frac{4x \Delta}{1 - 2 \Delta} \right) = 1. \end{equation} We finally have so \begin{equation} \limsup_{x \rightarrow \infty} \frac{g(x,N(x))}{f(x)} \leq \limsup_{x \rightarrow \infty} \frac{c(N(x)) \exp \left( \frac{2x}{1 - 2 \Delta} \right)}{\frac{1}{4} \exp \left( 2x - \gamma \right) + \mathcal{O}(e^{-2x})} = \frac{6}{e^{2 - \gamma}} < \frac{3}{2}. \end{equation} QED

Maurizio Barbato
  • 3,638