- #1

- 26

- 0

Suppose that the only paper money consists of 3-dollar bills and 10-dollar bills. Find what dollar amounts

can be made from a combination of these bills. Prove your result.

SOLUTION: Clearly the amounts $3, $6, $9, $10, $12, $13, $15, $16, $18 can all be made using 3-dollar bills and 10-dollar bills. In addition any amount greater than $17 be made as well. To prove this we use strong induction.

Base case: $18 can be made from 6 3-dollar bills, $19 can be made from one 10-dollar bill and three 3-dollar

bills. And of course, $20 can be made from two 10-dollar bills.

and the other example,

prove that every amount of postage of 12 cents or more can be formed using just 4-cent and

base case

we can form postage of 12, 13 ,14 ,15 cents using three 4-cent stamps, two 4- cents stamps ... etc this shows that P(12),P(13), P(14) and P(15) are true.