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. () Consider the greedy algorithm:

if (you could reach a gas station with a cheaper price on a full tank of gas) then {

-> buy the minimal amount of gas (possibly none) needed to the reach the cheapest such station, and drive to it;

}

Show that this strategy is not optimal. You should do this by providing an explicit counter-example.