Problem:
The sides of a circular track contain a sequence of cans of gasoline. The total amount in the cans is sufficient to enable a certain car to make one complete circuit of the track, and it could all fit into the car's gas tank at one time. Use mathematical induction to prove that it is possible to find an initial location for placing the car so that it will be able to traverse the entire track by using the various amounts of gasoline in the cans that it encounters along the way.
I tried several ways to prove this, always got stuck when it comes to whether the possible solution in P(k) or P(i) where 0
My attempt:
Base case:
when there is one can, clearly P(0) is true.
Inductive step:
Assume P(k) is true for all k is integer
Consider the k+1 case:
There exists at least one can M that has sufficent fuel to reach its neighbor can N, otherwise the total fuel would not be enough for a traverse
If we drive from M to N, dump all remaining fuel to N and ignore the distance from M to N, we then have a circle of k cans, which exists a starting can from where we can traverse the circle, let that trip be X.
HOWEVER, the direction of X doesn't have to be the same as the direction from M to N right? If they aren't the same, consider the case where N does not have enough fuel to get to M, from the inductive hypothesis we know it is possible that the car runs out of fuel upon reaching N and need the extra fuel from M to reach M itself (because we dump the remaining fuel from M to N). It is still possible that you may never reach M because in reality, if X has a reverse direction, you're "assuming" N has extra fuel from M while there actually isn't.
Answers online never mention the direction. Can anyone show me the a proof taking the direction of traverse into consideration or prove that the direction does not matter?