0
$\begingroup$

A bank has an unlimited supply of 3-peso and 5-peso notes. Prove that it can pay any number of pesos greater than 7.

So i'm not completely sure how to use strong induction, but the base case is pretty simple.

Base case:

n = 8,9,10

8 = 5 + 3; 9 = 3+3+3; 10= 5+5

Can anyone help me with the inductive step?

  • 0
    In case you're curious, there is such a thing as a 3-peso note. http://en.wikipedia.org/wiki/File:Cuban3Pesos.jpg2012-12-11

2 Answers 2

1

Suppose that $n>10$, and you can make any amount that is less than $n$ and greater than $8$; then you can certainly make $n-3$. Now, how can use that to make $n$? That is, if you can make $n-3$ with, say, $a$ $3$-peso and $b$ $5$-peso notes, how many of each can you use to make a total of $n$ pesos?

  • 0
    @kevlar: Oh, good! (For the *makes sense* part, not the *gets me*. :-))2012-12-12
0

Hint: For $n$ large (think about how large), how can we reduce the problem of paying $n$ pesos into paying a smaller amount? If we can do that, we are done by induction.