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

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

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

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