Thread: 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.

Thank you for your help in advance.

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.

Thank you for your help in advance.

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.

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.

Thank you for your help in advance.

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

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.

Hello, MathStudent1!

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

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.

Thank you Soroban. I am still working on the problem and trying to see it all.