Coin Problem - Wolfram Mathematica Puzzle
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!
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
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
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