Quant, Math & Computer Science Puzzles for Interview Preparation & Brain Teasing
A collection of ~225 Puzzles with Solutions (classified by difficulty and topic)

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:
If you have not done it already, please like / +1 / follow on: QuoraTwitterFacebookG+

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

18 comments:

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

    ReplyDelete
  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

    ReplyDelete
    Replies
    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



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

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

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

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

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

    ReplyDelete
  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

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

      Delete
  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

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

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

    ReplyDelete