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.

(In reply to re: solution - I don't think that proves the question by GOM)

"From what I gather, (and I'm not claiming to be anywhere near as smart as you, Charlie) but it sounded like what you said was if you start at the gas station (A, for ex.) where you would be at if the gas from the last station (Z) was barely enough to get you to that one (A) then you would you would have enough gas to go completely around the track without running out. But I don't see how you can be sure of that."

I don't think I said quite that.  Let's take a concrete example of what my methodology was:

Gas station 1 has 40% of the gas and is followed by 30% of the road.

Gas station 2 has 20% of the gas and is followed by 15% of the road.

Gas station 3 has 5% of the gas and is followed by 25% of the road.

Gas station 4 has 20% of the gas and is followed by 25% of the road.

Gas station 5 has 15% of the gas and is followed by 5% of the road.

On the preliminary imaginary trip you arbitrarily start at station 1 where you fill up with 40%.

By the time you get to station 2 you're down to 10%, but increase that to 30%.

By the time you get to station 3, you're down to 15%, but increase that to 20%.

By the time you get to station 4, you're down to -5%, but increase that to 15%.

By the time you get to station 5, you're down to -10%, but increase that to 5%.

By the time you get back to station 1, you're even at 0%.

Station 5 is where you reached the lowest, -10%, so that is where you actually should begin the trip.  Note that it was preceded by 25% of the roadway, at the beginning of which stretch was a station with only 20% of the gas, so it's not as if we looked for an exact match between gas and roadway stretch just before our choice of startoff point.

So, starting at station 5 on the real trip, we fill up with 15%, which declines to 10% by the time we get to station 1.

There we add 40% making 50%, which declines to 20% by the time we get to station 2.

There we add 20%, making 40%, which declines to 25% by the time you get to station 3.

There we add 5%, making 30%, which declines to 5% by the time you get to station 4.

There we add 20% making 25%, leaving just enough to get back to station 5 with an empty tank.  This is the only sense in which there is a "just enough" left, which is as it has to be.  We couldn't see where the "just enough" would be until we went through the exercise of finding the minimum point, allowing it to be negative on the mental trial run.

Posted by Charlie on 2004-06-03 22:20:26