A race car is set to make a lap around a track. The track has fuel depots spaced around it. If all the fuel from all the depots is put into the tank of the race car, it has exactly enough fuel to drive once around the track before running out of fuel.

The race car is to start at one of the depots, pick up the fuel and continue to the next, pick up that fuel, and so on until the car reaches its starting point or runs out of gas. (The car has no fuel before picking up the fuel at the starting depot.)

Is it always possible to choose a starting depot so the car can make the complete lap?

Choose one of the depot's arbitrarily as a starting point and plot the amount of gas remaining through the entire course, including spikes upward at each depot along the way, including at the beginning, where it jumps from zero to the amount at the chosen depot.  As this is only a preliminary thought experiment, allow the amount of fuel to go below zero if necessary, running on fuel "borrowed" from future fillings.

The tank will be empty at the end, as it was at the beginning before that first, immediate fill-up.

Take the point where the graph was lowest, probably a negative amount, in the likely case you hadn't chosen the best depot as the arbitrary starting point.  Make that depot of lowest gas tank the starting depot. This will have the effect of raising the graph so that all fuel levels are positive or at least are zero ready to spike upward as the zeros will occur only at a depot with gas ready.

Thus it is always possible to choose a depot so the car can make a complete lap.

Posted by Charlie on 2009-11-02 13:54:02