Proof by induction :-
Number of cars or length of track is N
[SEE THE EXAMPLE AT THE END IF YOU DON’T UNDERSTAND THE PROOF AND THEN READ THE PROOF]
Base :-
- Any one car with exactly fuel n , so we can start at this car and travel n units with this car basically to the initial point or exactly one time around the track.
K Number of cars with total sum of fuel n :-
- Consider k number of cars placed at some position at circular track of length n and the sum of fuel of all this cars are exactly n [ no two cars should be placed at same position].
- Now the trick is to find the possible placement of cars such that we can not reach any other car from the starting car.
For example — consider this :- let the first car is at the position 1 , (postion p is the point where the car number p was present in our orginal problem) , and it has fuel f1 , so we can reach 1 + f1 positons from the fuel of this car , so let’s place next car at 2 + f1 , and now if car 2 has f2 fuel we can reach 2+f1+f2 and lets place third car at 3+f1+f2. In this type of placement we are not wasting any postions and the last car is placed at k + f1 + f2 … + fk-1 = k + n - fk and this final car can travel form k + n - fk +1 to k where we can guarantee that there exists at least one car form which we can reach k ( k > fk) or the placement is not possible because there was already another car (k = fk) or from car k we can travel to 1 (k < fk ) meaning no matter where we place this last car there exists at least one car form which we can reach another car.
- Now we realize that there is no possible way to place all cars such that we can not reach another car for the fuel of previous car. Another way to say this is there is atleast one pair of cars exist such that we can reach second car from first car with the first car fuel alone.
- Now the another trick is consider the case of k cars with total fuel n , and we know there exits atleast one pair , consider this pair and replace this two cars by another car at the positon of first car with the fuel of sum of this two cars.
This replacement of pair of cars with new car doesn’t change our objective , because in the first case we are saying if we reach the first car we can get f1 fuel and if we reach second car we can get f2 fuel , but we know we can reach the second car with f1 fuel so , replacing the first car and second car with a car at first car position with fuel f1+f2 saying we can travel f1+f2 if we reach first car.
-
Now we have k-1 cars with the same total fuel of n , so we can guaranteed to find the another pair of cars. And do the step 4.
-
By doing this repeatedly we finally get 1 car at some position , this is the position where we can start our trip.
EXAMPLE :-
Consider the track of length of 6
Take 3 cars at position 1 5 6 with fuel 3 2 1
- from 1 we can travel upto 4 [ 1 - 2 - 3 - 4]
- from 5 we can travel upto 1 [5 - 6 - 1]
- from 6 we can travel upto 1 [ 6 - 1]
So there is atleast one pair of cars exist such that we can reach second car from first car with the first car fuel alone.
In this example there is three pairs , cars (2 ,3) , cars (2 , 1) and cars (3 , 1)
now take any pair let’s take cars (2 ,3) and combine.
Now we have a cars at positions 1 and 5 with fuel 3 and 3
- from 1 we can travel upto 4 [ 1 - 2 - 3 - 4]
- from 5 we can travel upto 1 [5 - 6 - 1 - 2]
here we have only one pair (2,1)
Combine them we left with one car at position 5 , which was our starting position for our initial problem.
If Something wrong with the proof let me know.