Exercise 10 Suppose there are n identical cars on a circular

Exercise 10. Suppose there are n identical cars on a circular track and among them there is enough gasoline for one car to make a complete loop around the track. Show that there is one car that can make it around the track by collecting all of the gasoline from each car that it passes as it moves

Solution

If there is a single car (n = 1), and that car has enough gas to make it around the loop, then it can make it around the loop, and we are done.
Assume the statement of the problem is true for n = k cars, and consider a situation with k + 1 cars on the loop. If we can find a particular car C1 that has enough gas to make it to the next car C2 then the situation is equivalent to transferring all of C2’s gas to C1 and eliminating C2 from the track. With one car eliminated, we know that there is a car that can complete the circuit from the induction hypothesis.
Suppose that no car has enough gas to make it to the next one. Then if each car drove forward as far as it could, there would be a gap in front of each one, so the total amount of gas would not be sufficient for one car to make it all the way around the track. Thus there must be a car that can make it to the next, and the proof is complete.When this problem was submitted in the first math circle, one of the students came up with a different solution that required no induction. Here it is:
Imagine the cars are on the track as before, but at first, instead of thinking of them as cars, just think of them as little fuel tanks. Add another phantom car to the track at any point with exactly enough fuel in its tank to make one complete loop. It can surely make it around, but as it goes around, imagine that it collects gas from each of the original cars. When it finishes, it will have exactly as much fuel as when it started, since it collected exactly the amount it burned during the loop. The amount of gas this phantom car has varies throughout the trip, having relative minima as it reaches each car/fuel-tank, where the fuel supply jumps up again. Pick the place where the phantom car has minimum gas. Clearly, if the phantom car had started there with an empty tank (at which point it would immediately get the gas from the minimal car), it could complete the loop since its tank would never get lower than it was at that point; namely, empty. That means that the car where this occurs could complete the route as required by the original problem. Figure 1 may help visualize this. The graph at the bottom represents the amount of gas in the tank of a phantom car that picks up no fuel on the way. It begins at A, and ends at B (which is just the same as A after a complete loop). The length AX represents enough fuel to make one loop, so after completing the loop, the tank is empty.
In the upper graph in the same figure, the phantom car begins with the same amount of fuel, but now there are four cars at C1, C2, C3 and C4. The lengths C1D1, et cetera represent the amount of gas in each of the cars. The four lengths, C1D1, C2D2 and so on, added together, are exactly equal in length to AX. This time, as soon as the phantom car’s position reaches each of the real cars Ci ,
its fuel increases by the amount by CiCi
. Clearly, it’ll have a full tank at the end, so will be again
at height X.
For this particular configuration, P4 is the point at which the phantom car’s tank is as low as it will ever get. If, instead of having C4P4 fuel at that point (at which point it would pick up the fuel from the fourth car), its tank were empty, it could still make the loop, since we know its fuel would never get below that. Thus car 4 could also make it, since it is in exactly the same condition as the phantom car, having just run out of fuel, and then taken on board car 4’s gasoline. Since the phantom car can make it, so will the fourth car