Showing there exists a sequence that majorizes another

The exact quantity of gas needed for a car to complete a single loop around a track is distrubuted among $n$ containers placed along the track. Show that there exists a point from which the car can start with an empty tank and complete the loop by collecting gas from tanks it encounters along the way. Assume that there is no limit to the amount of gas the car can carry.

Here is what I did:

Let the track have length $1$. Let $a_1,a_2,\dots a_n$ denote how much gas each of the $n$ gas containers distributed along the track in that order, clockwise. Note that $\sum_{i=1}^n a_i=1$. Let $d_1,d_2,\dots d_n$ denote the distance between containers $a_1,a_2$, containers $a_2,a_3$, $\dots$ and containers $a_n,a_1$, respectively (i.e. $d_i$ denotes the distance between the gas tanks $a_i$ and $a_{i+1}$, in the clockwise direction). Note that we also have $\sum_{i=1}^n d_i=1$. Now let $A_{k,j}=\sum_{i=j}^{j+k-1} a_i, D_{k,j}=\sum_{i=j}^{j+k-1} d_i$, where indices are taken mod $n$.

We would be done if we could show that there exists a $j$ such that the sequence $a_j,a_{j+1},\dots a_n, a_1, \dots a_{j-1}$ majorizes the sequence $d_j,d_{j+1},\dots d_n, d_1, \dots d_{j-1}$ (i.e. $A_{k,j}\geq D_{k,j}$ for all $1\leq k\leq n$). But I'm not sure how to show this. Also, I'm not even sure that this is true, since after you pick the $a_j$ you start with, you still need to pick which direction (clockwise or counterclockwise) around the circle.

Does anyone have any ideas on how to do this (or the problem in general?)

Solution 1:

First, as a thought experiment, start the car at an arbitrary point on the track, with a full tank of gas. Note down how much gas it has left immediately before reaching each container. When it returns to the starting point it will have exactly as much gas as it started with. This means it can keep going round the track indefinitely, as long as someone fills up each container between laps.

Look through your notes and find the lowest amount of gas just before one of the filling points. Stop the experiment and remove that much gas from the tank, and then let the car continue.

The car still keeps going indefinitely, but now whenever it comes to the chosen container it will run dry exactly when it reaches it. Starting at that point it will effectively start with an empty tank and complete the loop with fuel it picks up along the way, as specified.

In the new situation the car can't run dry between two containers, because that would mean that in the original experiment the fuel level just before the next container would have been less than what we removed, which contradicts how we chose the amount to remove.