Results 1 to 4 of 4

Math Help - How many ways you can make change for an amount N !

  1. #1
    Newbie
    Joined
    Jun 2014
    From
    Breslau
    Posts
    3

    Question How many ways you can make change for an amount N !

    Hello,

    I encountered a quite interesting problem. The question is: How many ways you can make change for an amount N using monets of value A and B, knowing that GCD(A,B)=1.
    Any idea how to solve this? It reminds me combinatorial class and generating functions. I would be grateful for any help!

    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,693
    Thanks
    1466

    Re: How many ways you can make change for an amount N !

    You only have the two coins of values "A" and "B"? The making change for amount "N" is asking for integers x and y such that Ax+ By= N. That is a "Diophantine equation" since it must be solved for integer x and y. This is more "number theory" than combinatorics,

    There is a standard method of solving linear Diophantine equations. That is to first solve Ax+ By= 1, then multiply solutions by N. The "Euclidean algorithm" gives a means of solving Ax+ By= 1, in integers as long as GCD(A, B)= 1, as given here. (If GCD(A, B) is NOT 1 it is impossible for there to be integer x and y such that Ax+ By= 1 since GCD(A, B) would be a factor of the left side but not the right.)

    For example, if A= 5 and B= 12, to solve 15x+ 22y= 37 (those numbers are made up arbitrarily), start by solving 15x+ 22y= 1. To do that I use the "Euclidean algorithm". I note that 15 divides into 22 once with remainder 7: 22- 15= 7. Then I note that 7 divides into 15 twice with remainder 1: 15- 2(7)= 1. (Since GCD(A, B)= 1 this method of dividing the preceding divisor by the preceding remainder will eventually give a remainder of 1.)

    Replace the "7" in 15- 2(7)= 1 with its expression from the previous equation: 7= 22- 15. We have 15- 2(22- 15)= 3(15)- 2(22)= 1. That tells us immediately the one solution to 15x+ 22y= 1 is x= 3 and y= -2.

    Now multiply x and y by N: x= 3N and y= -2N. They now satisfy 15x+ 22y= 15(3N)+ 22(-2N)= N. Further, it is easy to see that, for any integer ix, x= 3N- 22i and y= -2N+ 15i satisfy 15x+ 22y= 15(3N- 22i)+ 22(-2N+ 15i)= 45N- (15)(22i)- 44N- 22(15i)= N.

    To get positive x and y, we must have 3N- 22i> 0 and -2N+ 15i> 0. That is, we must have i< (3/22)N and i> (2/15)N. The problem is now to determine values of N for which the interval (2/15)N to (3/22)N contains at least one integer. That, in turn, will certainly be true as long as (3/22)N- (2/15)N= (3/22- 2/15)N is greater than 1 but may be true for smaller N. Of course 3/22- 2/15= 1/330.

    We can make change, with 15 and 22 value coins for any N larger than or equal to 330. Obviously we cannot make change for any value less than 15 but we can make change for N= 15. We cannot make change for N between 15 and 22 but can make change for N= 22. We cannot make change for any N between 22 and 15+ 22= 37 but can make change for 37. We cannot make change for any N between 37 and 2(15)+ 22= 52 but can make change for 52. We cannot make change for any N between 52 and 15+ 2(22)= 59 but can make change for 59. Continuing that way is tedious but the point of solving the Diophantine equation is that we know we can stop at N= 330 since we know we can make change for any N equal to or above 330.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jun 2014
    From
    Breslau
    Posts
    3

    Re: How many ways you can make change for an amount N !

    Hmm i mentioned about generating functions beacuse it was presented as useful tool for finding out on how many ways u can make change for N with given currency.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Jun 2014
    From
    Breslau
    Posts
    3

    Re: How many ways you can make change for an amount N !

    Ty for giving algorythm for solving this problem, unfortunately it only shows me how find the solution by myself for any N,A,B given. I looking for the homogeneous formula. I found somewhere that all ways of making change are presented by the following function G(x)=1/((1-x^A)(1-x^B))
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. New guy willing to make a change
    Posted in the New Users Forum
    Replies: 5
    Last Post: May 1st 2012, 04:58 AM
  2. How to make a change of basis?
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: October 5th 2011, 11:50 AM
  3. Replies: 6
    Last Post: September 19th 2010, 10:59 AM
  4. number of ways to make team
    Posted in the Statistics Forum
    Replies: 3
    Last Post: December 4th 2008, 03:23 AM
  5. how many ways to make change for 100 dollars?
    Posted in the Discrete Math Forum
    Replies: 11
    Last Post: May 8th 2008, 09:48 AM

Search Tags


/mathhelpforum @mathhelpforum