Gas Cans Around a Circular Track: A Lap Is Always Possible

Worked Solution

How to Think About It: The problem gives a global equality (total fuel equals lap length) and asks for a local guarantee (a good starting point). Induction works by finding a can that can reach its successor, merging the two, and recursing. Alternatively, think of the cumulative fuel balance around the loop, which returns to its starting value after a lap; start right after its minimum.

Approach: Give the induction proof for existence and the cumulative-minimum construction for finding the can.

Formal Solution:

*Step 1 -- Notation.* Number the cans $1, 2, \ldots, N$ in driving order. Let $g_i \ge 0$ be the fuel in can $i$ (measured in units of distance it can propel the car) and $d_i > 0$ the distance from can $i$ to can $i + 1$ (with can $N + 1$ meaning can $1$). The hypothesis is $\sum_{i=1}^{N} g_i = \sum_{i=1}^{N} d_i = L$, the lap length.

*Step 2 -- Base case.* For $N = 1$, the single can holds $g_1 = L$, so starting there you drive the full lap.

*Step 3 -- Inductive step.* Assume the claim holds for every configuration of $N$ cans, and consider $N + 1$ cans. There must be some can $i$ with $g_i \ge d_i$: otherwise $g_i < d_i$ for every $i$ and summing gives $\sum g_i < \sum d_i$, contradicting the equality of totals. Now form a new configuration with $N$ cans by removing can $i + 1$ and adding its fuel to can $i$: can $i$ now holds $g_i + g_{i+1}$ and the distance from it to the next remaining can is $d_i + d_{i+1}$. The totals still match, so by the induction hypothesis some starting can completes the lap in the merged configuration. The same starting can works in the original configuration: the only difference is that on the stretch from can $i$ to can $i + 2$ the car receives $g_{i+1}$ at can $i + 1$ instead of at can $i$; since $g_i \ge d_i$, the car reaches can $i + 1$ with a tank that is no lower than it was on arrival at can $i$, and from can $i + 1$ onward the fuel level is identical to the merged configuration. Hence a valid start exists for $N + 1$ cans, completing the induction.

*Step 4 -- Finding the can directly.* Define the cumulative balance after leaving can $k$ as $B_k = \sum_{i=1}^{k} (g_i - d_i)$, so $B_N = 0$ and $B_0 = 0$. Let $m$ be an index at which $B_m$ is minimal. Start at can $m + 1$ (can $1$ if $m = N$). Driving from can $m + 1$ and passing cans $m + 2, \ldots$, the fuel level on arrival at can $j$ is $B_{j-1} - B_m$ for $j > m$ (before picking up can $j$), and after wrapping around it is $B_N - B_m + B_{j-1} = B_{j-1} - B_m$ for $j \le m$. In both cases this is $\ge 0$ by minimality of $B_m$, so the tank never runs dry and the lap is completed. (Random configurations with the total-fuel constraint confirm that this rule always succeeds.)

Answer: Yes, always. Induction: with $N + 1$ cans some can holds enough fuel to reach the next one (else the total fuel would be less than the lap), so merging it with its successor gives an equivalent $N$-can problem, and a valid start for $N$ cans is valid for $N + 1$. Constructively, compute the running balance of fuel gained minus distance driven around the loop and start at the can immediately after the point where that balance is lowest.