3

Suppose that on a circular route, the gas stations located along the route contain just enough gas for one full trip. Prove that if one starts at the right gas station with an empty tank, one can complete the route.

The solution that is offered is:

Suppose that one with plenty of gas. So after completing the trip and emptying each gas station, one has the same amount of gas one started with. Notice that the fuel level is fluctuating, and at some station $k$ the amount of fuel left is minimized. Starting at station $k$ is the solution.

I suppose station $k$ is not unique, there can be multiple stations with the right amount of fuel? But my main question is if there is another way of proving this and can this problem be generalized?

grayQuant
  • 2,619

1 Answers1

1

I suppose station $k$ is not unique, there can be multiple stations with the right amount of fuel?

That's right. If there are multiple "minimal" stations, then the driver can start at any of these stations. By the time the driver arrives at the next minimal station, she will just have run out of gas, so she can fill up and continue on.

is [there] another way of proving this?

If we consider a necklace of the net change in gasoline for each fill-and-drive-to-the-next-station step, then this necklace's beads will add up to 0. Thus this problem is equivalent to showing that there's a way to orient the necklace such that all of the partial sums are non-negative.

can this problem be generalized?

Certainly! Here are a couple ideas:

  1. Instead of the route on a circular track, try a route which is an Eulerian circuit on some graph.
  2. The car could have a fuel efficiency which is a function of the amount of gas in the car.
Peter Kagey
  • 5,052