Circular race track

There is a circular race track, with n cars on it. On average, each car has 1/n laps worth of fuel. IE The total amount of fuel in the cars is just enough to run one lap.

Pick a car. We drive along with this car along our racetrack, until we run out of fuel, or meet another car. If we run out of fuel, we have failed. If we meet another car, we are allowed to steal all the fuel from that car for our own purposes. We continue this process until either we run out of fuel, in which case we fail, or we run one lap of the track, in which case we succeed.

For which n is it always possible to pick a car such that we will succeed?

Originally posted by Dejection
There is a circular race track, with n cars on it. On average, each car has 1/n laps worth of fuel. IE The total amount of fuel in the cars is just enough to run one lap.

Pick a car. We drive along with this car along our racetrack, until we run out of fuel, or meet another car. If we run out of fuel, we have failed. If we meet another car, we are allow ...[text shortened]... h case we succeed.

For which n is it always possible to pick a car such that we will succeed?

For all n.

Hm, david has answered all my recent problems very recently. David are you my double?

I invite everyone to prove that it is possible for all n.

Originally posted by Dejection
Hm, david has answered all my recent problems very recently. David are you my double?

I invite everyone to prove that it is possible for all n.

however they are spaced on the track there will only be two main cases

1. they will all be evenly spaced so exactly when the car you chose is going to run out of gas you meet another car thus stealing their gas...

2. There will be one car that can reach the next car without running out of gas thus providing enough gas to either finish the track or get to the next car. you must choose the car that is the farthest back car in this line or you wont be able to reach all the cars.

is this a sufficient explanation?

I think there is a misunderstanding here.
Not all the cars have the same amount of fuel, A car could have no fuel at all, or a full tank, we don't know.
My original post:
On average, each car has 1/n laps worth of fuel.

Certainly when n=1 😛

Uhuh, n=2 isn't too hard as well, it just gets hard when you try to consider all n...

If you can choose any car to start with then it can be done for all n. If you cannot choose the car to start with it is not necessarily possible for any n greater than 1 (as the car could have no fuel).

If there are two cars then one of them can get to the next to get the fuel and complete the circuit. so you can assume in effect that the second cars fuel is the first cars fuel and ignore the existence of the second car.

Using the same principle, assume it is true for n cars. If there is one more car added to make (n+1) and the fuel redistributed, there is bound to be the case where a car can reach the next one and take the fuel. In effect you can remove this car and treat it as if there are n cars.

If it is true for n cars it is true for n+1 cars.

We know it is true for n=1 and for that matter n=2 therefore true for all n

My method of looking at a particular case is as follows..

For each individual car, I look at whether or not it has fuel to reach the next car. A car which can reach the next car is considered linked to the next car, and a car which runs out of fuel is not linked to the next car. It is my contention that if there are at least 2 cars, at least one will be able to reach the next car.

After considering all cars, I then examine each set of linked cars, starting at the rear car. For purposes of this consideration, I treat the set of "linked" cars as though it consisted only of the first car with the combined fuel of all the cars in that chain, which follows all the principles of the first set of checks, only with fewer cars..

Eventually, since at least one link is always made (by my reckoning), you will eventually end up "linking" all the cars, and picking the rear car will allow you to make a full lap.

The only weakness is that I don't know exactly how to prove at least one car will be able to make it to the next car

Well done. I solved it the following way.
Suppose we have an imaginary car, that starts off with one lap worth of fuel. Let's put this imaginary car at exactly the same spot as one of our normal cars. So we run a lap along the track, taking fuel from each car we pass. Note that we cannot ever run out of fuel here, we start off with enough to finish the track. At the end of this, our imaginary car still has one lap of fuel in it. Now let us take a look at the graph of distance versus fuel in tank.

Our graph will start at 1, and fall downwards, and jump sharply up (when we meet a car and steal fuel), continue going down, and then up again, until we hit 1. Now we find the lowest point on this graph. This point must correspond to one of our original cars. Now we can discard our imaginary car, take this real car and drive. As we drive, we will not run out of fuel, becuause at no point in time will our fuel drop below what we started with. If it did, then we didn't pick the lowest point on our imaginary car graph.

The only weakness is that I don't know exactly how to prove at least one car will be able to make it to the next car[/b]

If the distance that could be covered by each car was considered, this must total one circuit. Either each car can just about reach the next or you must get overlaps.

(It is similar to the idea of having a number of pieces of string length 10cm. If you lay them out along a 10cm distance then either you have to lay each one where the last one ends or you have to overlap.)

I have just followed the Dejection's explanation involving the full car, it is an excellent explanation and the sort of short and elegant one that I wish I had noticed!