[grobber]

On a circular road there are some gas stations. Together, they have exactly as much gas as a car would need in order to go around the circle once. Prove that there is a gas station where you can start with an empty tank s.t. you can go around the circle.

I found it here.

[Sasha]

BTW it's Beijing 64.
Assume that car begins travel with the quantity of gas enough to go around the circle without supply. Take the station (or one of the stations) on which the quantity of gas is minimal. If we start from this station the quantity of gas always will be not less than the initial one (0).

[grobber]

Thanks! On that website the exact same solution is given. I think I have another one, but it might turn out to be the same .

A long time ago Moubinool posted a problem. I can't remember what it sounded like, but ti was similar to this: given some numbers around the circle s.t. their sum is , prove that we can choose one s.t. all the partial sums (in a clockwise direction) are . We can apply this here, considering the gas stations as positive numbers (because the car can get more fuel) and the gaps between them as negative numbers. My solution to this problem was, however, a bit longer.

[pbornsztein]

Yes Grobber, it was given in our 'Concours Gnral' in 1997 (I think), and it was, as you, the first thing which came to my mind while reading the statement of the problem.

Pierre.

[grobber]

I've tried to locate that problem recently, but failed . Do you happen to know where it was posted?

[darij grinberg]

This problem (the original one Grobber posted) is attributed to the Hungarian mathematician Laslo Lovas (spelling?) in David A. Klarner, The Mathematical Gardner, essay 5.4 by Ross Honsberger, with the same solution as Sasha gave.

Darij

[pbornsztein]

I've found that :
http://www.artofproblemsolving.com/Forum/viewtopic ... rs+general

Pierre.

[bambaman]

For 1 or 2 gas stations, it's trivial.
Let's assume that it's true for some n gas stations. Let's look at n+1 stations: there must be at least one station that has enough gas to arrive at the next station. If we look at this station and the station after it as one station, than we have n stations, and by the assumption, we're done.
So by induction, it's true for every n.