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?

Suppose there are only two stations.  Since the total fuel is just enough to complete the course, starting at one of the stations will give you enough fuel to reach the second, but starting at the other won't.  Intuitively, it is always possible for the car to make the full circle when the number of stations is two.

Assume that it is true for 'k' stations.

Now add one more station, 'k+1'.  Clearly there has to be at least one pair of adjacent stations (i and i+1) where a car starting at station 'i' will have enough fuel to make it to 'i+1'.  Now do the gedanken experiment of physically moving the fuel from station "i+1' to station 'i'.  This doesn't change anything regarding whether the conjecture is true or not.  But it does mean that now there are only 'k' stations.

So, it's true for two stations.  If it's true for 'k' stations then it's also true for 'k+1' stations.

So it's true, by induction.

Posted by Larry on 2009-11-03 02:23:00