## Feb 10, 2014

### Coin Problem - Wolfram Mathematica Puzzle

Source: The super awesome puzzle blog by Gowtham Kumar - Puzzle Tweeter - Coin Problem who got it from Wolfram Mathematica

Problem:
Suppose you have an infinite stock of \$a bills and \$b bills such that g.c.d(a,b)=1. Find the largest amount of money (integer) that cannot be represented using \$a and \$b denominations.

Shameless plug:

Update (21 June 2014):
Solution: Posted by Raunak Kudesia, Sid Hollander and me (Pratik) in comments!

1. If I recall correctly, Kapil Hari Paranjpe also asked this question in nurture program.

2. Ans: ab-a-b?

Let the max number which cannot be represented using a and b denominations.

Now,
x+a=yb
x+b=za
This implies,
yb-a=za-b
-> b(y+1)=a(z+1)
Since a and b are co-prime, z=nb-1 and y=na-1
This gives x = nab-a-b

If n>1, let n=j+k
x= jab+kab-a-b
> x= a(jb-1) +b(ka-1), which cannot be true .

Therefore, n=1 and X= ab-a-b

1. Awesome solution. Thanks

Just to explain your solution in more detail:

Let us say that the maximum number that cannot be represented using a and b denominations is X.
So, X+a is pa+yb, p>=0, y>=0
Now, since X cannot be represented in the form of (pos number)*a + (pos number)*b
p=0
So, X + a = yb for some y

Similarly, X+b = za

So, a(z+1) = b(y+1)

Since a and b are coprime, z=nb-1 and y=na-1 where n is integer
X = nab-a-b

If n>1, let n = j+k where j>0, k>0

X = a(jb-1) + b(ka-1)

which is not possible.

So, n = 1, and X = ab - a - b

Thanks a ton

2. @pratik: Could you please explain you first statement.
if x is max number that can be represented using a and b denominations it means
x is not of form (m*a+n*b)
So, (x+a) would also not be in form of (m'*a+n*b)
but according to you, X+a is pa+yb, p>=0, y>=0. How??

3. (ab) - (a+b)

see ...Coin problem from Wikipedia ....and Frobenius number

Snip...."With only 2 pence and 5 pence coins, one cannot make 3 pence, but one can make any higher amount.
The coin problem (also referred to as the Frobenius coin problem or Frobenius problem, after the mathematician Ferdinand Frobenius) is a mathematical problem that asks for the largest monetary amount that cannot be obtained using only coins of specified denominations.[1] For example, the largest amount that cannot be obtained using only coins of 3 and 5 units is 7 units. The solution to this problem for a given set of coin denominations is called the Frobenius number of the set......

4. What happens when values of a and b are 2 and 3 respectively?

1. What's the problem with that?

5. Are the values of a and b greater than 2?

1. Why do you need that?

6. The answer seems to me is
ab - (a + b).
I have to think for a possible explanation. I am pretty inductivist !! :-D

7. Since gcd(a,b)=1, then the set t={ au+bv | au+bv>0, a and b are positive integers} will have all the multiples of gcd i.e all no. from 1 to infinity.So,any amount can be represented

1. You have not considered u,v should be non negative . But in the problem it is considered.

8. Anshuman, if a=3 and b=7 how would you represent 11?
Clearly formula
ab - (a + b)
gives 11 as max number that cab NOT be represented

9. My bad.I now realise that u,v can only be 0 or positive,

10. Its really nice posting. I think it would be helpful for all. Thank you for sharing with us.
Mathematica

### Fraction Brainteaser

Source: Sent to me by Gaurav Sinha Problem: Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20...