Consider the problem of making change for n cents using the fewest number of coins. Assume that we live in a country where coins come in k dierent denominations c1, c2, . . . , ck, such that the coin values are positive integers, k ≥ 1, and c1 = 1, i.e., there are pennies, so there is a solution for every value of n. For example, in case of the US coins, k = 4, c1 = 1, c2 = 5, c3 = 10, c4 = 25, i.e., there are pennies, nickels, dimes, and quarters. To give optimal change in the US for n cents, it is sucient to pick as many quarters as possible, then as many dimes as possible, then as many nickels as possible, and nally give the rest in pennies. Give an example of coin denominations, such that using the above strategy of picking the maximum number of coins of the largest denomination will not lead to an optimal solution, i.e. will not minimize the number of coins in the change.