A car running out of gas on a circular track

The sides of a circular track contain $n$ gas stations. All gas stations are running out of gasoline and the total amount of gasoline in the gas stations is just enough to enable a certain car to complete a lap. Prove that there exists an initial location on the track such that if the car starts with an empty tank from that location, then it will be able to travel the entire track by buying gasoline from the gas stations that it encounters along the way.

Answer

Imagine an additional similar car B with a very large tank which has more than enough gas to complete a lap. Let the car B start from an arbitrary gas station on the circular track, buy all the gas from the gas stations it encounters, and complete a lap. Let $G _1$ ​ be a gas stations where the level of gas in the car B is the lowest when B arrives at $G_1$. If the car $A$ with an empty tank starts from $G_1$ ​ and travels in the same direction as the car B, then it will be able to complete a lap by buying gas from the gas stations it encounters along the way. Indeed, if A runs out of gas between the gas stations $G_i$  ​and $G_{i+1}$ ​ for some $1\leq i \leq n-1 $, then the amount of gas required to travel from $G_1$ ​ to $G_{i+1}$ ​ is more than the total amount of gas available in stations $G_1, \cdots, G_{i+1}$. This implies that the level of gas in the car B at station $G_i$ ​ was strictly lower than the level of gas when it arrived at station $G_1$. This is a contradiction and the proof is complete.

Erdos Erdos
4.6K
The answer is accepted.
Join Matchmaticians Affiliate Marketing Program to earn up to 50% commission on every question your affiliated users ask or answer.