Viewing 2 posts - 1 through 2 (of 2 total)
  • Author
    Posts
  • #74724
    Abhisruta Maity
    Participant

    There are n identical cars on a circular track. Among all of them, they have just enough gas for one car to complete a lap. Show that there is a car which can complete a lap by collecting gas from the other cars on its way around.

    #74853
    Saumik Karfa
    Participant

    Solution From Problem Solving Strategies by A Engel:

    The theorem is obvious for (n=1 .) Suppose we have proven the theorem for (n). Let there be (n+1) cars. Then there is a car (A) which can reach the next car (B). (If no car could reach the next car, there would not be enough fuel for one lap.) Let us empty (B) into (A) and remove (B). Now we have (n) cars which, between them, have enough fuel for one lap. By the induction hypothesis, there is a car which can complete a lap. The same car can also get around the track with all ((n+1)) cars on the road. From (A) to (B,) there will be enough gas (from car (A) ) and, on the remaining road sections, this car has the same amount of gas as in the case of (n) cars.

Viewing 2 posts - 1 through 2 (of 2 total)
  • You must be logged in to reply to this topic.
linkedin facebook pinterest youtube rss twitter instagram facebook-blank rss-blank linkedin-blank pinterest youtube twitter instagram