Assume that you live in a country where the only currency are 3$ and $10 dollar
ID: 1948401 • Letter: A
Question
Assume that you live in a country where the only currency are 3$ and $10 dollar bills. Show that every amount greater than $17 can be made from these bills. Let P(n) be the statement that a postage of n cents can be formed using just 4 and 7 cent stamps. Use strong induction to prove that P(n) is true for n >=(greater than or equal to) 18.
Explanation / Answer
first base step 18 = 4*1 + 7*2 now let n can be formed using 4 and 7 n = 4*p + 7*q then if q>0 n+1 = 4*p + 7*(q-1) + 4*2 and if q=0 then we can be sure that p>=5 because n>17 then n+1 = 4*(p-5) + 7*(q+3) so if we can form n then we can form n+1 for n>=18