**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:**

If you have not done it already, please like / +1 / follow on: Quora, Twitter, Facebook, G+

Update (21 June 2014):

**Solution:**Posted by Raunak Kudesia, Sid Hollander and me (Pratik) in comments!
If I recall correctly, Kapil Hari Paranjpe also asked this question in nurture program.

ReplyDeleteYep :-)

DeleteAns: ab-a-b?

ReplyDeleteLet 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

Awesome solution. Thanks

DeleteJust 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

@pratik: Could you please explain you first statement.

Deleteif 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??

(ab) - (a+b)

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

Thanks

DeleteWhat happens when values of a and b are 2 and 3 respectively?

ReplyDeleteWhat's the problem with that?

DeleteAre the values of a and b greater than 2?

ReplyDeleteWhy do you need that?

DeleteThe answer seems to me is

ReplyDeleteab - (a + b).

I have to think for a possible explanation. I am pretty inductivist !! :-D

:-)

DeleteSince 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

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

DeleteAnshuman, if a=3 and b=7 how would you represent 11?

ReplyDeleteClearly formula

ab - (a + b)

gives 11 as max number that cab NOT be represented

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

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

ReplyDeleteMathematica