Gas stations on a circular track

On a circular track, there are several gas stations. The total amount of gas in all these stations are just enough for a car to complete one lap. Prove that, starting with an empty car, one can choose an initial position such that he can complete the lap by subsequently filling gas in these stations.

Solution

First Solution

Let $n$ be the number of gas station. Proof by induction. The problem is trivial for $n=1$ or $n=2$. Now, let $A$ be a gas station with enough gas to reach the next one. Such station must exist, otherwise the total fuel in all stations would not be enough to complete one lap. Let $B$ be the station after $A$.

We delete $A$ and $B$ and replace them with a station $A'$ that contains the combined gas of both $A$ and $B$. Now we have $n-1$ stations, and therefore there exist a way to complete the lap. We choose the same starting position, and when we get to $A'$, now we get to $A$ instead. Since $A$ has enough gas to get to $B$, we can continue driving.

Second Solution

Choose an arbitrary gas station as a starting point, and suppose we allow negative gas for the time being. Also suppose that at the end of the first lap, each station is replenished so that we can complete another lap. This way, we will complete two identical laps. We graph the amount of gas with respect to time.

The graph will be a linear function with negative slope with a few "spikes" (step function) added in. Let $T$ be the time required to complete a lap. The graph will pass by $(0,0)$ and $(0,a)$ for some positive $a$ that represents the first station. It will also pass by $(T,0)$. Since the second lap is identical to the first one, the graph from $T$ to $2T$ is identical to $0$ to $T$. That is, it passes through $(T,0), (T,a), (2T,0)$.

Take the minimum of the graph. There are two minimum points, one for each lap (there might be more if this minimum happens multiple times throughout the lap). Take the first one. That minimum must correspond to a gas station, because it can only happen right before a spike, otherwise the graph would only continue to go down from there. Now if we start at that station, we will never reach a situation where we have negative gas. Starting from that station is akin to translating the graph so that the minimum point becomes the origin. Since we have two laps, we don't need to worry about cut and pasting the rest of the graph. Simple translations would accurately reflect the graph for the first lap, and we can simply trim the left and right unused part of the graph.