Suppose that the only currency were 3-dollar bills and 10-dollar bills. Show that every amount greater than 17 dollars could be made from a combination of these bills.

Question

Quizplus · Accepted Answer

The Answer is We find that 18 dollars can be made using six 3-dollar bills. Now suppose that

n

dollars can be formed, where

n \geq 18

. Suppose that at least two 10 -dollar bills were used. Then two 10 -dollar bills can be replaced by seven 3-dollar bills to form

n + 1

dollars. Otherwise, if zero or one 10 -dollar bill were used, then at least three 3-dollar bills were used. Then replace three 3 -dollar bills by one 10 -dollar bill to form

n + 1

dollars.

Suppose That the Only Currency Were 3-Dollar Bills and 10-Dollar