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?

1.  Does it matter which direction we go around the track?

No we can find a starting depot either way since the solutions given are reversible.

2.  Will a starting depot that works in one direction always work in the other direction?

No.  Consider two depots spaced 1/3 of a lap apart each with half the fuel.  Each depot is the correct starting place for opposite directions.

3.  Do the paths for opposite directions have anything in common?

Yes.  When traveling on one direction there will be some pick-up at which the amount of fuel is at a maximum for the lap.  This depot is the correct starting point for the opposite direction.  This can be seen by using Charlies jagged graph example.  The paths for opposite directions are mirrored about the distance axis (not the fuel axis.)  A starting point should be where the graph is lowest but when this is mirrored this is the previous high point.

Posted by Jer on 2009-11-03 15:15:28