Jeep problem

This is a classic "jeep problem" (desert crossing) variant. The tanker starts with $3000$ gallons at Port A, must travel $1000$ miles to Port B, loses $1$ gallon per mile, and has capacity $1000$ gallons. The goal is to maximize delivered oil.

Key insight: The optimal strategy uses intermediate depots and shuttles oil forward in stages, each stage moving a certain amount of oil a certain distance while consuming fuel for round trips. The number of trips decreases by one each stage.

Let $D = 1000$ miles, capacity $C = 1000$ gallons, initial fuel $F = 3000$ gallons. Consumption is $1$ gallon per mile.

General principle: To move $n$ full loads (i.e., $n \times 1000$ gallons) a distance $d$, you make $n$ forward trips and $n-1$ return trips, consuming $(2n-1)d$ gallons. The amount delivered forward is $nC - (2n-1)d$.

Stage 1: Start with $3000$ gallons at A, i.e., $n_1 = 3$ loads. Move forward distance $d_1$ such that after shuttling we have exactly $n_2 = 2$ loads ($2000$ gallons) at the next depot. Fuel consumed: $(2\cdot3-1)d_1 = 5d_1$. Remaining: $3000 - 5d_1 = 2000 \Rightarrow d_1 = 200$ miles.

Stage 2: At mile $200$, we have $2000$ gallons ($n_2 = 2$ loads). Move forward distance $d_2$ to reduce to $1$ load ($1000$ gallons). Fuel consumed: $(2\cdot2-1)d_2 = 3d_2$. Remaining: $2000 - 3d_2 = 1000 \Rightarrow d_2 = 333\frac{1}{3}$ miles.

Stage 3: At mile $200 + 333\frac{1}{3} = 533\frac{1}{3}$, we have $1000$ gallons ($n_3 = 1$ load). Drive directly to B, which is $1000 - 533\frac{1}{3} = 466\frac{2}{3}$ miles away. Fuel consumed: $466\frac{2}{3}$ gallons. Delivered: $1000 - 466\frac{2}{3} = 533\frac{1}{3}$ gallons.

Thus the maximum deliverable is $533\frac{1}{3}$ gallons, which rounds to $533$ gallons.

Verification: Total fuel consumed = $5\times200 + 3\times333\frac{1}{3} + 1\times466\frac{2}{3} = 1000 + 1000 + 466\frac{2}{3} = 2466\frac{2}{3}$ gallons, matching $3000 - 533\frac{1}{3}$. Total distance traveled = same sum, confirming consumption rate.