Suppose that a coin system has values 1, c_2, and c_3 with 1 < c_2 < c_3. We say that the coin system is non-canonical if and only if there exists an amount x > 1 for which the greedy algorithm for giving change does not produce the fewest number of coins (i.e., the greedy algorithm is not optimal). Show that (1, c_2, c_3) is non-canonical if and only if the quotient q and remainder r of dividing c_3 by c_2, that is, c_3 = qc_2 + r with 0 r < c_2, satisfy 0 < r < c_2 q. [Hint: You can freely use the fact proven by Kozen and Zaks that the smallest counterexample x is in the range c_3 + 1 < x < c_2 + c3. Show that the smallest counterexample x uses just coins of value c_2 in the optimal solution, and only coins of value 1 and c_3 in the greedy solution.

Please dont post the picture of the book as the answer