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.

I want to propose this for the "MORE CRYPTIC SOLUTION OF THE YEAR" award ;-)

1st (a lemma) If from station A (with M liters) you can reach station B (with N liters), then if station B didn't exist but station A had M+N liters, starting at A you could go exactly as far as before. (Proof left to the reader!)

2nd (another lemma) If there are two or more stations, there must be at least one station such that you can reach the next one. (Again, proof left to the reader!)

3rd (an algorithm) While there are two or more stations, pick two consecutive stations that satisfy the 2nd lemma, add the liters of the 2nd station to the 1st one, and erase the 2nd one.

4th (the conclusion) At the end, you'll have only one station left, with the L liters (yet once more, proof left to the reader!) having proved the theorem.

Posted by Federico Kereki on 2004-06-03 14:08:47