Exercise 1257Combinatorics › Counting principlesOlympiadAdded 4 Nov 2026

Gas stations on a circular road

#cyclic sequences#prefix sums#extremal choice#cycle lemma

Statement

There are $n$ gas stations $S_1,\dots,S_n$ along a circular road, in this cyclic order. Station $S_i$ sells $g_i$ units of fuel and the stretch of road from $S_i$ to $S_{i+1}$ (with $S_{n+1}=S_1$ ) needs $d_i$ units of fuel. The total fuel available is at least the total fuel needed: $\sum g_i\ge\sum d_i$ . A car with an empty tank (and unlimited tank capacity) starts at one of the stations, takes all the fuel there, and drives on. Show that one can choose the starting station so that the car completes the full circle without ever running out of fuel.

Hint

Put $a_i=g_i-d_i$ and look at the partial sums $s_k=a_1+\dots+a_k$ . Where should the car start relative to the smallest partial sum?

Show solutionHide solution

Solution

Setup. Let $s_0=0$ and $s_k=a_1+\dots+a_k$ , so that $s_n=\sum g_i-\sum d_i\ge0$ . Let $m\in\{0,1,\dots,n-1\}$ be an index minimising $s_m$ among $s_0,\dots,s_{n-1}$ . Start at station $S_{m+1}$ .

The car never runs out. The fuel left on arrival at the station after having driven $k-m$ stretches is $s_k-s_m$ for $m<k\le n$ , and $s_n-s_m+s_j$ after wrapping around.

For $m<k\le n-1$ and $k=n$ : $s_k-s_m\ge0$ because $s_m$ is the minimum of $s_0,\dots,s_{n-1}$ (for $k=n$ we use $s_n\ge0=s_0\ge s_m$ ).
After wrapping: $s_n+s_j-s_m\ge s_j-s_m\ge0$ .

All fuel-on-arrival amounts are non-negative, so the car never runs dry.

Remark. If $\sum g_i=\sum d_i$ the start is unique up to the stations where the minimum is attained. This is the cycle lemma.

Lesson. On a cycle, start right after the minimum of the prefix sums.

Gas stations on a circular road

Statement

Solution

More problems in Counting principles