hard | discrete |
Several gas stations on a circular trek have between them just enough gas for one car to make a complete round trip. Prove that if you start at the right station with an empty tank you shall be able to make it all the way around.
Induction
Take N=2 gas stations. Assume their capacities are x1 and x2 (in terms of distance). Now, x1+x2 = 1. Assume y1 and y2 be clockwise distances from 1 to 2 and 2 to 1 (clockwise), y1+y2 = 1. Hence we cant have x1<y1 and x2<y2 both. Thus, let x1 >= y1. In this case we start with station 1 and complete the journey. Assume the path is possible for N=K stations, we want to prove for N = K+1 stations, using same argument as above, xi>=yi for some i, and hence reaching xi with zero fuel ensures reaching x(i+1). Thus we merge xi and x(i+1), and the problem is reduced to N=K stations, which we assumed!
Another method is to imagine having a big tank with enough gas for a round trip and enough room for going through the motions of emptying every gas station on your way. Start at any station and mind to record the amount of gasoline on reaching gas stations on your way around. At the end of the trip, when you pull into the station of departure with the original amount of gas, check your list. The station marked with the least number is the one where you want to start on an empty tank.