Gas stations on a circular road hold, in total, just enough gas for one lap.
logic/gas.stations New
New entry, edited from material collected for the archive and not yet in a released version.
Problem
Gas stations on a circular road hold, in total, just enough gas for one lap. Prove that, starting with an empty tank, you can complete the loop from at least one of the stations. Consider a circular loop of a road. There are n gas stations placed at random on it. The total amount of all the gas that these stations carry collectively allows you to drive around the loop exactly once. You start from a station by filling a prior empty tank. Assuming no limit on the amount of gas you can store, prove that there is at least one station from where you can start and complete the loop. -- Ajit Pendse <cmpend@lsuvm.bitnet>
Show solution
Begin at any of the N stations and make a graph of fuel on board vs.
distance. If the fuel goes negative, don't worry about it... just keep
graphing. The function you get will look something like
|\
| \ |\ |\
| \ | \ | \
| \| \ | \
| \ |\ | \
-----------------------
\|
0 1 2 3 0
This shows us starting at gas station 0 where we load 5 units of fuel.
We use up 4 units driving to gas station 1 where we load 3 more units
and so on. Notice that when we arrive at station 2 we have -1 units of
fuel on board, and that we end up back at gas station 0 with all of our
gas exhausted.
Now, this function has a constant slope (save where it is undefined)
which represents the rate of fuel consumption per unit distance. The
points of discontinuity represent gas stations, and the vertical
displacement at each gas station represents the amount of gas
available at that station. Neither the slope nor these displacements
would change had we started at some gas station other than station 0.
What would change would be the absolute vertical position of the
graph, for if we start a station K, then the car will begin with the
amount of gas stored at station K and will return to station K empty.
So...
Using the graph we just created, find the minimum value that our fuel
function achieves. This minimum cannot be positive. If it is 0, we
have already found a starting point that gets us around the loop. If
it is less than zero, pick a station where this minimum is achieved
(if there is more than one choose one arbitrarily) and start there.
This will force the graph to reach 0 at that station, and it will thus
be greater than or equal to zero everywhere else, and hence we have
found a starting point which will get us around the loop.
(This is, of course, just a sketch of a proof. In particular, you
might find it interesting to consider how one knows that the minimum
value for the function will occur at a gas station... or for that
matter, how one knows that there will be a minimum value. :)
-- Paul Lafollette <lafollet@astro.ocis.temple.edu>