\documentclass[11pt]{article}
\include{18313-preamble}
\usepackage{graphicx}

\begin{document}
\lecture{2004/05/07}{Dan Ports}{2004/05/17}{drkp@mit.edu}
\lecturetitle{The Jeep Problem: A More General Solution}{C. G. Phipps,
  The American Mathematical Monthly, Vol. 54, No. 8. (Oct.,
  1947)}{?}{Dan Ports}


\section{The problem}
\label{sec:problem}


The Jeep Problem is a classic optimization problem, originally
formulated long before there were jeeps to name the problem after.

\paragraph{Problem: (The Jeep Problem)}
Suppose that a jeep can carry a maximum of $n$ gallons of gas and can
travel $c$ miles per gallon. What is the minimum (or greatest lower
bound) amount of gas required to cross a desert $x$ miles wide?

Note that we can assume without loss of generality that $n = c = 1$
and thus eliminate them from consideration; this simply changes the
units of $x$, without affecting the problem in any interesting way.

\paragraph{Problem: (The Generalized Jeep Problem)}
Suppose $m$ jeeps fully loaded with gasoline wish to travel the
furthest distance possible. What is the greatest distance a single
jeep from the caravan can travel if:
\begin{enumerate}
\item none return to the initial position
\item all return to the initial position
\item all but one return to the initial position
\end{enumerate}

Note that it is not hard to show that a solution that maximizes the
distance traveled for a particular initial amount of gasoline is
equivalent to a solution which minimizes the amount of gasoline
required to travel a given distance. We are in this case solving the
latter problem, but a special case of this can be shown to be
equivalent to the non-general problem stated first.

We now consider each of these three cases.


\section{No jeeps return}
\label{sec:none-return}

In this case, at various points some jeeps will transfer their
gasoline to other jeeps and be abandoned. This allows the final
remaining jeep to use not just its gas but that of other jeeps to
travel the maximum distance possible.

We first note that one load of gasoline has been consumed at a
distance of $\frac{1}{m}$ units --- since we define one unit to be the
distance one jeep can travel on its load of gas, and there are $m$
jeeps. At this point, each jeep will have $1 - \frac{1}{m}$ units of
gasoline, and if the gasoline from one jeep is redistributed to the
other $m-1$ jeeps, each jeep will have
\[1 - \frac{1}{m} + \frac{1}{m-1}\left(1- \frac{1}{m}\right) = 1\]
units of gasoline available: a full load. The empty jeep is abandoned.

The remaining jeeps can then proceed another $\frac{1}{m-1}$ units.
Recursively applying this procedure, we obtain a maximum distance
traveled of
\[\sum_{i=1}^m \frac{1}{i} = 1 + \frac{1}{2} + \frac{1}{3} + \cdots +
\frac{1}{m-1} + \frac{1}{m}\] This is a pleasing result, since it is
the harmonic series, which diverges. Thus, with an infinite supply of
jeeps\footnote{The environmentalists love this solution.}, any
distance can be traveled. Of course, the $\Theta(\log n)$ growth rate
of the harmonic series makes this rather inefficient, but it is
possible.

This is the optimal solution to this problem. To see why, we consider
the two other possibilities.

\begin{itemize}
\item If the first jeep were abandoned before the $\frac{1}{m}$ unit
  mark, more gasoline would be available than the rest of the caravan
  could hold. This would have to go to waste. The jeeps would travel
  fully loaded, but from an earlier point. This is clearly a less
  optimal solution.
\item If the first jeep were to be abandoned after the $\frac{1}{m}$
  unit mark, it would be traveling for the distance between the
  $\frac{1}{m}$ mark and wherever it is actually abandoned. During
  this period, it is consuming gasoline, i.e. the caravan is consuming
  gasoline at a rate of $m$ units rather than $m-1$. Since the
  gasoline it contains could have been transferred to the other jeeps
  in the caravan at the $\frac{1}{m}$ mark, in which case they would
  be consuming gasoline at a rate of $m-1$, this is less optimal.
\end{itemize}

Note also that the in the final stage of the solution, the last jeep
will be traveling with a full load of gasoline, i.e. it will travel a
distance of 1 unit. It is easy to see that this is clearly optimal: it
maximizes the distance in which only a single jeep is traveling, when
the fuel consumption of the caravan is at its minimum.


\section{All jeeps return}
\label{sec:all-return}

We now require all jeeps to return to their starting point. This is s
simple variation on the previous case. Instead of traveling a distance
$\frac{1}{m}$ before redistributing the gas, we instead travel half
that distance, $\frac{1}{2m}$, and deposit half of the caravan's gas
at that point. We then proceed as described above. When each jeep is
emptied of its gas, instead of abandoning it, it uses the gasoline in
the fuel dumps along the way to travel back to the starting point.

So the jeep that travels the furthest in the caravan will travel a
distance of
\[\sum_{i=1}^m \frac{1}{2i} = \frac{1}{2} + \frac{1}{4} + \frac{1}{7} + \cdots +
\frac{1}{2m-2} + \frac{1}{2m}\] Note that it is also possible to
deposit fuel at shorter intervals than we do above, but this adds
nothing to the solution, so for simplicity we simply deposit fuel
according to the procedure above, which minimizes the number of fuel
dumps.


\section{All jeeps but one return}
\label{sec:all-but-one}

We now consider the case in which all jeeps except for the last are
required to return to the starting point. In this case, the optimal
distance is $\frac{1}{2m-1}$ instead of $\frac{1}{m}$ or
$\frac{1}{2m}$. This is because at the first stage, $m$ jeeps travel
that distance, and $m-1$ will return. So at a distance of
$\frac{1}{2m-1}$, the traffic, including the return leg, will consume
exactly one full load of gasoline. This is the ideal distance to
travel: by the same argument as in the previous cases, traveling
further or traveling less will be sub-optimal.

So the one jeep in the caravan that does not return will travel a
distance of
\[\sum_{i=1}^m \frac{1}{2i-1} = 1 + \frac{1}{3} + \frac{1}{5} + \cdots +
\frac{1}{2m-3} + \frac{1}{2m-1}\]

It turns out that this problem is identical to the non-generalized
Jeep Problem, in which there is only one Jeep, but it can return to
the starting point as many times as necessary to pick up more gas, and
deposit the gas at various fuel dumps in the desert. Note that the
solution in this case does not specify anything about \emph{when} in
the sequence the jeeps must return to the starting point. 

It is equally valid to say that the first jeep travels to the
$\frac{1}{2m-1}$ point, deposits all the gasoline except what it needs
to return, then travels back to the starting point, and then the
second jeep sets out for the $\frac{1}{2m-3}$ point, stopping along
the way to take some gasoline from the fuel dump that the first jeep
set up. In this case, there is no requirement for the individual jeeps
to actually be separate --- they may all be the same jeep, making
multiple trips! Thus this result is also the solution for the
non-generalized problem in which there is only one jeep traveling as
far as possible.

\bibliographystyle{IEEEtran}
\nocite{fine}
\nocite{phipps}
\bibliography{18313}
\end{document}