lxiii. Jeep Problem

Problem (Fine 1947, Phipps 1947). A jeep holds 1 unit of fuel and drives 1 unit of distance per unit of fuel. At the base there are $n$ units. The jeep may leave fuel in depots anywhere along its way and pick it up later. How far into the desert can it get (exploration: one way), and how far can it get and still come back (round trip)?

Variant	Maximum distance with $n$ units	Growth
one way (exploration, “desert crossing”)	$\sum _{k=1}^n\frac{1}{2k-1}=1+\frac{1}{3}+\frac{1}{5}+\cdots$	$\approx \frac{1}{2}\ln n+\ln 2+\frac{\gamma }{2}$
round trip (back to base)	$\sum _{k=1}^n\frac{1}{2k}=\frac{H_n}{2}$	$\approx \frac{1}{2}\ln n+\frac{\gamma }{2}$
fractional fuel $f=n+r$, $0\le r<1$	add $\frac{r}{2n+1}$ (one way) or $\frac{r}{2n+2}$ (round trip)
fuel needed for distance $D$	exponential in $D$: about $e^{2D}$ up to a constant factor

$n$	1	2	3	4	5	10
one way	1	1.333	1.533	1.676	1.787	2.133
round trip	0.5	0.75	0.917	1.042	1.142	1.464

Plan (one way). Work backwards from the end: with $k$ units at a depot, move them all forward by $\frac{1}{2k-1}$ using $k$ trips forward and $k-1$ trips back ($2k-1$ traversals, one unit burnt), arriving with $k-1$ units; finally drive the last full tank 1 unit.

double jeepOneWay(double f) {                        // f >= 1 units of fuel
    int n = int(f); double r = f - n, d = r / (2 * n + 1);
    for (int k = 1; k <= n; k++) d += 1.0 / (2 * k - 1);
    return d;
}
double jeepRoundTrip(double f) {
    int n = int(f); double r = f - n, d = r / (2 * n + 2);
    for (int k = 1; k <= n; k++) d += 1.0 / (2 * k);
    return d;
}
 
// Simulate the one-way plan for integer n, checking tank and depot accounting. Returns the distance reached.
double simulateJeep(int n) {
    double pos = 0, depot = n;                       // all remaining fuel sits at the current depot
    for (int k = n; k >= 2; k--) {
        double step = 1.0 / (2 * k - 1), next = 0;
        for (int trip = 1; trip <= k; trip++) {
            double take = min(1.0, depot); depot -= take;   // fill the tank (capacity 1)
            double tank = take - step;               // drive forward
            assert(tank >= -1e-12);
            if (trip < k) { double drop = tank - step; assert(drop >= -1e-12); next += drop; }   // keep just enough to drive back
            else next += tank;                       // last trip: stay at the new depot with everything
        }
        assert(depot < 1e-9); pos += step; depot = next;
        assert(fabs(depot - (k - 1)) < 1e-9);
    }
    return pos + min(1.0, depot);                    // final full tank
}

Proof: the plan works and nothing can go further

Plan. At a depot with $k\ge 2$ units, $k$ trips each fill the tank: the first $k-1$ trips drive $\delta =\frac{1}{2k-1}$, drop $1-2\delta$ and return; the last drives $\delta$ and stays. Fuel arriving at the new depot: $(k-1)(1-2\delta )+(1-\delta )=k-(2k-1)\delta =k-1$, and the tank never exceeds 1. So from $n$ units the jeep reaches ${\sum }_{k=2}^n\frac{1}{2k-1}$ with exactly one unit, then drives 1 more. A fractional amount $r$ is moved first: with $n+r$ units, $n+1$ trips forward and $n$ back burn $(2n+1)\delta$; choosing $\delta =\frac{r}{2n+1}$ leaves exactly $n$ units. Round trip: every forward traversal is matched by a return, so each stage uses $2k$ traversals and advances $\frac{1}{2k}$.

Upper bound (one way). For $x>0$ let $F(x)$ be the net fuel carried across the point $x$ outward over the whole trip; since all fuel starts at the base, $F(x)$ equals the fuel burnt or left beyond $x$, so $F$ is non-increasing, $F(0^{+})\le f$, and $F(x)>0$ for every $x$ the jeep passes. Each outward crossing of $x$ carries at most 1 unit, so there are at least $\lceil F(x)\rceil$ of them; as the jeep finishes beyond $x$, it crosses back one time fewer. For $h>0$, the fuel burnt inside $(x,x+h]$ is at most $F(x)-F(x+h)$ (it crossed $x$ outward and did not cross $x+h$), and it is at least $h$ times the number of traversals of the interval, at least $(2\lceil F(x+h)\rceil -1)h$. Hence while $F$ lies in $(k-1,k]$ it falls at rate at least $2k-1$ per unit of distance, so the jeep can cover at most $\frac{1}{2k-1}$ while $F$ is in that band (at most $\frac{r}{2n+1}$ in the top band $(n,n+r]$). Summing the bands gives the formula. Round trip: inward crossings equal outward ones, so the rate is at least $2k$ and the bound is $\sum \frac{1}{2k}$. Growth: ${\sum }_{k\le n}\frac{1}{2k-1}=H_{2n}-\frac{1}{2}{H}_n$ and $H_m=\ln m+\gamma +o(1)$. Checked: the simulated plan reaches jeepOneWay(n) for $n\le 50$ with all tank and depot checks passing.

Related notes

• Harmonic Lemma and Floor Sums
• Ant on a Rubber Rope (another harmonic-series puzzle)
• Bridge and Torch (shuttling resources)