# Induction Problem

• Feb 12th 2007, 05:05 PM
MathStudent1
Induction Problem
Suppose you are in a country that has bank notes of value \$3 and \$5 only. Prove that it is possible to pay (without requiring change) for any item which is worth a whole number of dollars greater than \$7.

• Feb 12th 2007, 05:09 PM
ThePerfectHacker
Quote:

Originally Posted by MathStudent1
Suppose you are in a country that has bank notes of value \$3 and \$5 only. Prove that it is possible to pay (without requiring change) for any item which is worth a whole number of dollars greater than \$7.

This is the Frobenius coin problem for n=2.
The general idea is that whenever gcd(3,5)=1 you can go on forever eventually.

This formula in this case is,
(x-1)(y-1)=(5-1)(3-2)=8
Thus, 8 is the smallest number from where everything is obtainable, or you can think of it as 7 is the largest number from which no combination is possible.
• Feb 12th 2007, 08:46 PM
CaptainBlack
Quote:

Originally Posted by MathStudent1
Suppose you are in a country that has bank notes of value \$3 and \$5 only. Prove that it is possible to pay (without requiring change) for any item which is worth a whole number of dollars greater than \$7.

Suppose that you can make some total n>15, If no 5's are used then convert
5x3's to 3x5's, So we can always make n with at least 1x5.

Now add 2x3 and take away 1x5, so we have now made n+1. So if there
is any total N>15 which we can make with 3's and 5's then by induction
we have proven that we can make any total n>N.

Let N=\$20, then we can make it as 5x3+1x5, hence we have proven that
any total >\$20 can be made with \$3 and \$5 bills by induction.

(Note with a bit more care we can reduce the mimimum sum that can be
made to the the \$8 in ImPerfectHackers post, but the question does not
ask for a tight lower limit, so we don't need that complication).

RonL
• Feb 13th 2007, 10:44 AM
MathStudent1
Thank you CaptainBlack. I guess I don't see how this problem is an induction problem? I am familiar with doing induction problems that involve summation or inequalities. Thanks again.
• Feb 14th 2007, 01:19 PM
Soroban
Hello, MathStudent1!

I think I can hammer this into an Induction proof . . .

Quote:

Suppose you are in a country that has bank notes of value \$3 and \$5 only.
Prove that it is possible to pay (without requiring change) for any item
which is worth a whole number of dollars greater than \$7.

Since the value (V) is greater than 7: .V > 8.

S(1): The first case is V = 8, which can be made with 3 + 5.

Assume S(k): that V = k can be expressed as a combination of 3's and/or 5's.

We must prove S(k+1): that k + 1 can be expressed as a combination of 3's and/or 5's.

There are two possible cases for the value of k:

(1) k is a multiple of 3. .Then k = 3a, for some integer a.
. . .Since k > 8, a must be at least 3. .There are at least three \$3 bank notes.
Then we can create k + 1 by adding two \$5 notes and removing three \$3 notes.

(2) k is not a multiple of 3. .There is at least one \$5 bank note.
Then we can create k + 1 by adding two \$3 bank notes and removing one \$5 dollar bank note.

In either case, given k dollars, we can create k+1 dollars.

We have proved that: .S(k) . .S(k+1).
. . The induction proof is complete.

• Feb 15th 2007, 09:33 AM
MathStudent1
Thank you Soroban. I am still working on the problem and trying to see it all.