Let An = { a1, a2, ..., an } be a finite set of distinct coin types (e.g., a1= 50 cents, a2= 25 cents, a3= 10 cents etc.). We assume each a_i is an integer and that a1 > a2 > ... > a_n. Each type is available in unlimited quantity. The coin changing problem is to make up an exact amount C using a minimum total number of coins. C is an integer > 0.

(a) Explain that if an != 1 then there exists a finite set of coin types and a C for which there is no solution to the coin changing problem.

(b) When a_n = 1 a greedy solution to the problem will make change by using the coin types in the order a1, a2, ..., a_n. When coin type a_i is being considered, as many coins of this type as possible will be given. Write an algorithm based on this strategy.

(c) Give a counterexample to show that the algorithm in (b) doesn't necessarily generate solutions that use the minimum total number of coins.

d) Show that if An = { k^_n-1, k^_n-2, ..., k^₀ } for some k > 1 then the greedy method in (b) always yields solutions with a minimum number of coins.