There is a point on the road from where the car with initially empty fuel tank can complete a loop. I need help proving the following statement:
There are $n$ gas stations along a circular road. The total amount of fuel at these stations is exactly the amount needed for a car to complete one loop. Show that there is a point on the road from where the car with initially empty fuel tank can complete a loop.
Here is my progress:
Note that a successful starting point must always be at one of the gas stations since; otherwise, the car will not be able to move due to the empty fuel tank. Before tackling the proof, consider the following example with four gas stations. Label the gas stations
$g_1, g_2, g_3, g_4$
so that the amount of fuel at gas station $g_i$ is $x_i$ for $1 \leq i \leq 4$. Define the distance between consecutive gas stations to be $d(g_i, g_{i+1})$. Then $x_1 + x_2 + x_3 + x_4 = 1$ and $d(g_1, g_{2}) + d(g_2, g_{3}) + d(g_3, g_4) + d(g_4, g_1) = 1$. We want to make $d(g_i, g_{i+1})$ and $x_1, ..., x_4$ arbitrary so; for example, consider $x_1 =0.2,x_2 = 0.3 ,x_3 = 0.4, x_4= 0.1$ and $d(g_1, g_{2}) = 0.3 , d(g_2, g_{3}) = 0.1 , d(g_3, g_4)= 0.2, d(g_4, g_1) = 0.4$. We want to find a starting gas station so that we can get back to it. If the starting point is at $g_2$ and fill the car with fuel, call it $X$, we have $X=0.3$. We can then travel to the next gas station $g_3$ but will be left with $X = 0.3 - d(g_2, g_{3}) = 0.2$. After fueling at $g_3$, $X = 0.7$ and traveling to $g_4$ we have $X= 0.7 - d(g_3, g_4) = 0.5$. After fueling at $g_4$, $X = 0.6$ and traveling to $g_1$ we have $X= 0.6 - d(g_4, g_1) = 0.2$. Therefore, we have completed a loop so at least one starting point exists and that is at $g_2$.
claim:
If $\sum_{i =1}^k x_i = 1$ and $\sum_{i=1}^k d(g_i, g_{i+1}) = 1$
then there exists an $x_i$ where $i = 1, ..., k$ such that $x_i \geq d(g_i, g_{i+1})$.
proof of claim:
By way of contradiction suppose $x_i < d(g_i, g_{i+1})$
for some $1 \leq i \leq k$. Then, $\sum_{i=1}^k d(g_i, g_{i+1}) = 1$ implies $\sum_{i = 1}^k x_i < 1$ which is a contradiction.
proof of problem:
We induct on the number of gas stations. Suppose there is only one gas station along the circular road such that the total amount of fuel at this station is exactly the amount needed for a car to complete one loop. Therefore, there is only one possible starting point for the car which is at the single gas station. Now, suppose there is always a successful starting point when there are $k$ gas stations. That is, for gas stations
$g_1, ..., g_k$ with fuel amounts of $x_1, ..., x_k$, respectively, such that $d(g_1, g_2) + ...+ d(g_k, g_1) = 1$ and $x_1 + ... + x_k = 1$.
The total amount of fuel at the
$k$ stations is exactly the amount needed for a car to complete one loop. We want to show that there is always a successful starting point when there are $k+1$ gas stations so consider a gas station with $k+1$ gas stations. By the claim above, there is at least one gas station that contains enough gas to reach the next gas station, call this gas station $h_1$ and consider the gas station that comes
after
$h_1$; call it, $h_2$.
I am not sure where to go from here.
An idea:
Combining the fuel from $h_1$, $h_2$ and proceeding up to $h_k$, we have enough fuel for a car with an initial empty fuel tank to make a loop so that a starting point exists, namely at $h_1$.
But how do we know that the fuel from $h_2$ will get us to the next gas station?
 A: You don't know that the fuel from $h_2$ will get you to the next station.
The inductive hypothesis is that there is always a successful loop for any $k$ stations. You do know that given $k+1$ stations with total fuel exactly equal to the amount of fuel required to complete one loop, there must be at least one station that has enough fuel to get to the next station.
I find it more convenient if you number the stations so that station $g_k$ is a station that has enough fuel to reach the next station, $g_{k+1}$.
Now if the fuel at $g_{k+1}$ were added to the fuel at $g_k$ instead of being placed at $g_{k+1}$, we would have a road with $k$ stations with exactly enough fuel to complete one loop, and we know we can start the loop somewhere and complete it successfully.
Suppose the solution for $g_1,\ldots,g_k$ is to start the loop at $g_i$ for some $1 \leq i \leq k.$
Then we know the gas at $g_i, \ldots, g_{k-1}$ is distributed so that we can get to $g_k$ starting at $g_i$; the original fuel stores at $g_k$ and $g_{k+1},$ now combined at $g_k$, together with the leftover gas from $g_i, \ldots, g_{k-1}$ are sufficient to get to $g_1$; and the leftover gas from $g_i, \ldots, g_k$ at $g_1$ together with the gas stored at $g_1$ is a sufficient amount for the car to continue traveling all the way to $g_i$ without running out of gas between stations.
Now restore the amounts of fuel at $g_{k+1}$
Then for the original configuration $g_1,\ldots,g_k,g_{k+1}$,
show that you can get from $g_i$ to $g_k$ without running out of fuel,
from $g_k$ to $g_1$ without running out of fuel, and from $g_1$ to $g_i$ without running out of fuel.
Note that this still works if $i = 1$ or $i = k$; it is trivial to get from $g_1$ to $g_1$ (for example) without running out of fuel regardless of the fuel already in the car's tank.
A: Let me take a somewhat different approach. Starting from any given gas station, you can get some distance around the loop before running out of gas. So some starting point will get you the maximum possible distance around the loop. We might as well number things so that gas station $1$ is a distance-maximal starting point.
Now if the maximum distance isn't the complete loop, then we must have run out of gas with at least one station unvisited. Let's say we fell short of gas station $m\le n$. Now a bit of backward induction takes over: there couldn't be enough gas in station $n$ to get to station $1$, or we would have done better by starting at station $n$ instead of station $1$. Likewise, there couldn't be enough gas in stations $n-1$ and $n$ combined to get from station $n-1$ to station $1$. And so forth, down to station $m$. But this is a contradiction: the combined gas in stations $m$ to $n$ is enough to drive the entire rest of the way, from where you ran out of gas all the way to station $1$, so it must be more than enough to get from station $m$ to station $1$.
