Suppose a race track in the shape of a simple closed curve (i.e. it does not intersect itself), and suppose that distributed along it, in any way whatsoever, are N gas stations. Suppose that a race car needs L liters of gas to go completely around the track, and that the sum of the gas available at the N stations is exactly L.

Consider that the car cannot move without gas (*assume it can't travel by momentum alone, thus it MUST need gas to move*), and that it has constant mileage (consumption of gas is directly proportional to the distance the car moves, and depends on nothing else).

Prove that there exists at least one gas station such that, starting from it, the car can do a full lap.

Assuming, as SK has noted, that the gas tank is large enough to hold as much gas as will be necessary per this:

Start at any arbitrary point on the track. In your imagination, plot, with distance along the track as the x coordinate and amount of gas in the tank as the y coordinate, an entire traverse of the course.  Allow the amount of gas to go negative--this is only imaginative.  The graph will be a sawtooth.  At each station, the amount shoots up vertically; between stations the amount goes down at a constant slope.

When the course is completed, there's the same amount in the tank as at the beginning, as the gas loaded along the way exactly balances the distance traveled.

Choose the low point on the graph as the starting point, with both zero and the amount of gas available there (it is at a station) as values, as the tank is filled without travelling.  Since this is the low point on the graph, the gas level will never go below zero.

Only if the high point on the graph (now raised so that the low point on the graph is zero rather than negative) were above the capacity of the gas tank would the trip be impossible.

Posted by Charlie on 2004-06-03 14:35:15