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 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.
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
Hello, MathStudent1!
I think I can hammer this into an Induction proof . . .
Since the value (V) is greater than 7: .V > 8.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.
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.