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.

Printable View

- February 12th 2007, 05:05 PMMathStudent1Induction 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. - February 12th 2007, 05:09 PMThePerfectHacker

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. - February 12th 2007, 08:46 PMCaptainBlack
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**Im**PerfectHackers post, but the question does not

ask for a tight lower limit, so we don't need that complication).

RonL - February 13th 2007, 10:44 AMMathStudent1
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.

- February 14th 2007, 01:19 PMSoroban
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.

__>__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.

- February 15th 2007, 09:33 AMMathStudent1
Thank you Soroban. I am still working on the problem and trying to see it all.