Suppose at each mile post a0, a1, . . . , an there is a gas station. You start out with u units of gas in your gas tank at mile post a0 and you want to get to mile post an. Your cars gas tank has a capacity of c units of gas and your car gets R miles per unit of gas. You can stop at any mile post along the way and buy as much gas as you like. However, the following constraint must always be satisfied: The amount of gas in your tank should never go below 0 or above c. ()

(a) Suppose the goal is to plan your trip so that you make as few stops as possible along the way to buy gas. Consider the following simple greedy strategy:

while (you are not at the destination) do{

-> fill up your tank at the current location,

-> drive to the farthest gas station you can reach on a full tank of gas

}

Prove that this strategy results in an itinerary that minimizes the number of stops.

Hint: Prove by induction on n