I don't know how to start a proof, but the gist of the method would be to start in the area of greatest concentration, and moving away from the area of least concentration.
The problem is, this could be one spot with a lot, or several very close locatons with a high percentage of the fuel.
If the distribution is close to even, then it's possible to have several solutions. For instance, if the fuel is spread evenly such that every spot has equal amounts of fuel, then all sets of starting points and direction work.
Originally posted by geepamoogleRead the thread.
I don't know how to start a proof, but the gist of the method would be to start in the area of greatest concentration, and moving away from the area of least concentration.
The problem is, this could be one spot with a lot, or several very close locatons with a high percentage of the fuel.
If the distribution is close to even, then it's possible to ...[text shortened]... hat every spot has equal amounts of fuel, then all sets of starting points and direction work.
For the purposes of my argument I will assume that the total amount of fuel is 1 unit and the total distance is 1 unit. This means that each interval of distance requires an equal amount of fuel, i.e. going halfway around the track requires half a unit of fuel. This won't affect the validity of the conclusion.
Given the starting point, for every point on the track we need the distance from the start to that point to be less than or equal to the fuel available from the start to that point. Otherwise, our fuel would run out when the distance travelled starts to exceed the fuel picked up.
Suppose we have a starting point on the track. Imagine a graph of fuel picked up versus distance travelled from the start. On the x axis we have distance travelled, from 0 to 1. On the y axis we have fuel-picked-up. Fuel-picked-up at distance 0 will be 0, and fuel-picked-up at distance 1 will be 1. The fuel-picked-up function will increase (and never decrease), going from 0 to 1. For a given starting point to work, the fuel-picked-up function must always stay on or above the line y=x, that is the line of fuel-picked-up = distance travelled, because fuel-picked-up must be greater than or equal to distance travelled or we run out of fuel.
So here is the problem: we have to show that we can pick a starting point on the track so that if we draw such graph of fuel-picked-up versus distance, the line will always be above y=x of slope 1, no matter how the fuel is distributed.
Pick any point on the track, and draw the graph for that point. Only, draw it for *two* loops around the track. Now we have distance going from 0 to 2 on the x axis and fuel-picked-up going from 0 to 2 on the y axis. The second half of the graph, representing the second loop around the track, is an exact copy of the first, but shifted 1 unit right and 1 unit up. It has the property that if the point (x, y) is on the line in the first half of the graph, the point (x+1, y+1) is on the line in the second half of the graph. This is just saying that if from any point on the track you go for one more loop around the track, you will pick up 1 more unit of fuel, since there is 1 unit distributed around the entire track. If you've picked up y units of fuel after x revolutions, you will have picked up y+1 units of fuel after x+1 revolutions.
So we have our extended graph, representing the fuel picked up over two trips around the track. Now, imagine a straight line of slope 1 below the graph. The line slowly approaches the curvy line representing fuel-picked-up versus distance. The straight line stops moving exactly when it touches the fuel-versus-distance line. In fact, the two lines must intersect (at least) *twice*, once in the first half of the graph and once in the second half. Because we've just seen that if they touch at (a, b) in the first half they must also touch at (a+1, b+1) in the second half.
So, if the lines touch at (a, b) and (a+1, b+1) imagine the portion of the graph from x = a to x = a+1, the revolution around the track starting at point a. Now, the straight line started out below the fuel-versus-distance function and has never crossed it, only just touched it. So in the section of the graph from (a,b) to (a+1, b+1), the fuel-versus-distance function *always lies above the straight line of slope 1*. This is exactly what we need to have a driveable path! Thus the point a, where the line of slope 1 touches the fuel-versus-distance line, is the starting point we seek. We can find this point for any distribution of fuel around the track.
I guess that's probably a very confusing proof, as it tries to describe visual ideas with mere text. I hope it made some sense?
After reading Xanthos's post (which relies on the same concept as mine, but is much simpler), here is, I think, a simpler proof:
Pick any point on the track. Graph the amount of fuel you would have at every point if you started from the point. Find the absolute minimum of this graph. Say this occurs at point P on the track. Now, if we start from P, we can make it all the way around the track. At every point on the track we will have more fuel than we will at P, because P is the absolute minimum of the graph. If we start at P, when we have no fuel, we will always have more than no fuel and thus we will be able to keep going until we get back to P.