Kvant Math Problem 82

Let the cars be arranged around the circle in their order along the road.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m51s
Source on kvant.digital

Problem

Several identical automobiles are parked along a circular road. It is known that if all the gasoline contained in these automobiles were poured into a single car, then that car could travel all the way around the circular road and return to its starting point. Prove that at least one of the cars on the road can make a complete circuit of the ring, collecting gasoline from the other cars along the way.

Exploration

Let the cars be arranged around the circle in their order along the road. Denote by $d_i$ the amount of gasoline needed to travel from car $i$ to the next car, and by $g_i$ the amount of gasoline initially contained in car $i$.

The condition of the problem says that

$$g_1+\cdots+g_n \ge d_1+\cdots+d_n,$$

because all gasoline poured into one car suffices for a complete circuit.

The statement resembles the classical gas station problem. A natural conjecture is that some starting car allows a full tour if one collects the gasoline encountered along the route.

Consider a small example. Suppose

$$(g_1,g_2,g_3)=(1,0,5),\qquad (d_1,d_2,d_3)=(2,2,2).$$

The total gasoline equals the total requirement. Starting from car $1$ fails immediately. Starting from car $2$ also fails. Starting from car $3$ succeeds. This suggests that the successful car need not be unique.

A useful reformulation is to introduce net gains

$$a_i=g_i-d_i.$$

Then

$$a_1+\cdots+a_n\ge 0.$$

If a car starts at position $k$, then after passing several stations its fuel equals a partial sum of the corresponding $a_i$'s. Thus the problem becomes: given a cyclic sequence whose total sum is nonnegative, show that some cyclic starting point makes all successive partial sums nonnegative.

The place most likely to hide an error is the passage from a global condition, the total sum being nonnegative, to the existence of a cyclic starting point with all partial sums nonnegative. That step requires a precise argument.

A standard idea is to choose a position immediately after a minimum of the cumulative sums. If

$$S_0=0,\qquad S_i=a_1+\cdots+a_i,$$

and $S_m$ is the minimum among all $S_i$, then starting at $m+1$ should work because every later cumulative sum is at least $S_m$. This appears to be the core insight.

Problem Understanding

We have several cars parked around a circular road. Car $i$ contains some amount of gasoline. A car can stop at the other parked cars and take all their gasoline. The total gasoline in all cars together is sufficient for one complete circuit of the ring.

We must prove that at least one of the cars can start from its own position, travel around the entire circle, collect gasoline from every other car encountered, and return to its starting point.

This is a Type B problem. The goal is to prove the stated existence claim.

The core difficulty is converting the global hypothesis, sufficient total gasoline for one circuit, into a local statement guaranteeing a starting position from which fuel never becomes negative during the trip.

Proof Architecture

Define $g_i$ as the gasoline in the $i$-th car and $d_i$ as the gasoline required to travel from car $i$ to the next car; then $\sum g_i\ge\sum d_i$ by hypothesis.

Define $a_i=g_i-d_i$; then $\sum a_i\ge0$, and the fuel carried by a touring car is described by partial sums of the $a_i$.

Let $S_0=0$ and $S_i=a_1+\cdots+a_i$; choose an index $m$ for which $S_m$ is minimal among $S_0,S_1,\dots,S_n$.

Lemma: Starting immediately after the minimum cumulative sum $S_m$, every cyclic partial sum is nonnegative. This follows because every cumulative sum differs from $S_m$ by a nonnegative amount.

The hardest part is proving the lemma for partial sums that wrap around the end of the cycle.

Solution

Number the cars consecutively around the circular road. Let $g_i$ be the amount of gasoline initially contained in the $i$-th car, and let $d_i$ be the amount of gasoline required to travel from car $i$ to the next car. Indices are taken modulo $n$.

Since all gasoline from all cars, when poured into one car, suffices for a complete circuit, we have

$$g_1+\cdots+g_n \ge d_1+\cdots+d_n.$$

Define

$$a_i=g_i-d_i.$$

Then

$$a_1+\cdots+a_n\ge0.$$

Now set

$$S_0=0,\qquad S_i=a_1+\cdots+a_i\quad (1\le i\le n).$$

Choose $m$ so that

$$S_m=\min{S_0,S_1,\dots,S_n}.$$

We claim that the car at position $m+1$ can make a complete circuit.

Suppose this car starts with the gasoline $g_{m+1}$ contained in it. After collecting gasoline from each visited car and paying the fuel cost of each traversed road segment, the amount of fuel in the tank after traversing $r$ consecutive segments equals

$$a_{m+1}+a_{m+2}+\cdots+a_{m+r},$$

where indices are interpreted cyclically.

We must show that this quantity is never negative.

First consider the case in which $m+r\le n$. Then

$$a_{m+1}+\cdots+a_{m+r} = S_{m+r}-S_m.$$

Since $S_m$ is the minimum of all cumulative sums,

$$S_{m+r}-S_m\ge0.$$

Now consider the case in which the route wraps around the end of the cycle. Write $m+r=n+t$ with $1\le t\le m$. Then

$$\begin{aligned} a_{m+1}+\cdots+a_n+a_1+\cdots+a_t &=(S_n-S_m)+S_t. \end{aligned}$$

Because $S_m$ is minimal, we have $S_t\ge S_m$. Hence

$$\begin{aligned} (S_n-S_m)+S_t &\ge (S_n-S_m)+S_m\ &=S_n. \end{aligned}$$

But

$$S_n=a_1+\cdots+a_n\ge0.$$

Therefore every cyclic partial sum beginning at $m+1$ is nonnegative.

The fuel in the moving car is exactly these cyclic partial sums. Since none of them is negative, the car never runs out of gasoline before reaching the next parked car. Consequently it can travel from car to car around the entire ring, collecting gasoline at each one, and eventually return to its starting point.

This completes the proof.

∎

Verification of Key Steps

The first delicate step is the identification of the fuel after $r$ traversed segments with the cyclic partial sum

$$a_{m+1}+\cdots+a_{m+r}.$$

After leaving car $m+1$, the car gains $g_{m+1}$ units of gasoline and spends $d_{m+1}$ units reaching the next car. The net change is $a_{m+1}$. Repeating the same accounting at each subsequent car shows that the fuel after $r$ segments is exactly the stated sum.

The second delicate step is the wrapped case. For $m+r=n+t$,

$$a_{m+1}+\cdots+a_n+a_1+\cdots+a_t = (S_n-S_m)+S_t.$$

A careless argument might replace $S_t$ by $0$ and conclude only that the quantity is at least $S_n-S_m$, which need not be nonnegative. The crucial input is the minimality of $S_m$, yielding $S_t\ge S_m$ and therefore

$$(S_n-S_m)+S_t\ge S_n.$$

The third delicate step is the use of the hypothesis. The assumption about the total gasoline is needed only once:

$$S_n=\sum_{i=1}^n(g_i-d_i) = \sum_{i=1}^n g_i-\sum_{i=1}^n d_i \ge0.$$

Without this inequality, the wrapped partial sums could become negative even if $S_m$ were chosen as a minimum.

Alternative Approaches

Another proof uses an elimination process. If a car cannot reach the next car, merge it with that next car, treating their combined gasoline as belonging to a single super-car. The total gasoline and the validity of the statement are preserved. Repeating the operation reduces the number of cars. Eventually only one car remains. Since the total gasoline suffices for a full circuit, that remaining car can traverse the circle. Reversing the mergers shows that one of the original cars could also complete the circuit.

The cumulative-sum argument is preferable because it identifies a successful starting position explicitly, namely the car immediately following a minimum of the prefix sums. It also gives a direct quantitative description of why the fuel level never becomes negative.