Coin Sum Problem

  • I
  • Thread starter Arman777
  • Start date
  • #1
1,777
139

Main Question or Discussion Point

Let's suppose there are 4 types of coin, 1p 2p 5p and 10p. The problem is, we need to find total combinations which the sum of the coins gives us the 200p.

I am trying to find a mathematical equation to solve the problem but I am stuck. First I started to think algebraically. And I have this,
$$x+2y+5z+10k=200$$

Now lets think a simple case where we need to find the number of (x,y) such that satisfies this equation.
$$x+2y=200$$

Lets rewrite this as $$y=(200-x)/2$$ which you can imagine a graph that crosses y=100 and x=200. In this case every point on the line satisfies this equation but we know that (16.5,91.75 ) cannot be counted as a solution since 16.5x1p or 91.75x2p dont make sense. Hence in this solution only the positive (x,y) integers will survive. In this case there will be 101 solutions for this problem.

Lets try to do same thing for $$x+2y+5z=200$$
in this case I am kind of stuck. I tried to think like this, This corresponds to a plane in 3D. So if we can find the number of the points on the triangle which stands between the axis then we can find the solution but it seems kind of harder. I tried to find to area of the triangle which it can be calculated using the determinant of the points where the plane crosses the axis so I have (200,0,0) (0,100,0) and (0,0,40) and the area is 10954 and then I take the coefficients and the result is (1,0,0) (0,2,0) and (0,0,5) and I have 5.67 so I said the total points in that area is 10954/5.6 put of course that doesnt worked well. The answer should be 2081 but I had 1928.

So I cannot find an answer using this I can find for a line but not for an area.

The next think I thought was something like this,
$$x/200+y/100+z/40=1$$
so we know that (x,y,z) should be positive integers but now I am again stuck. Is there any formula for this kind of things or something that I can derive ?

Or more importantly can we derive the solution one of the above approaches.

Here my main purpose is find a general solution for any type of equation such that,

$$a_0x+a_1x_1+a_2x_2...=S$$ for every given integer $$a_n$$ and a given $$S$$ how many combinations are possible ?
 
Last edited:

Answers and Replies

  • #2
Stephen Tashi
Science Advisor
7,175
1,315
Let's suppose there are 4 types of coin, 1p 2p 5p and 10p. The problem is, we need to find total combinations which the sum of the coins gives us the 200p.
You might find an ingenious way to thrash this out in detail, but the conventional way to solve such problems is to use "generating functions". I haven't tried them on this particular problem, but I suggest you have a look at the generating function technique. Search for keywords "generating function, coin, change" and you get relevant results (e.g. http://www.3dmatics.com/blog/2012/10/generating-functions-part1/ )

Your problem would be transformed to the following equivalent problem:

In the formal product of all the factors :
## ( (x^1)^0 + (x^1)^1 + (x^1)^2 + ...)##
##( (x^2)^0 + (x^2)^1 + (x^2)^2 + ...)##
##( (x^5)^0 + (x^5)^1 + (x^5)^2 + ...)##
##( (x^{10})^0 + (x^{10})^1 + (x^{10})^2 + ...)##

what is the coefficient of the term involving ##x^{200}## after all like terms are combined?

It's worth learning about generating functions even if there is a better way to solve your particular problem!
 
  • Like
Likes StoneTemplePython
  • #3
1,777
139
You might find an ingenious way to thrash this out in detail, but the conventional way to solve such problems is to use "generating functions". I haven't tried them on this particular problem, but I suggest you have a look at the generating function technique. Search for keywords "generating function, coin, change" and you get relevant results (e.g. http://www.3dmatics.com/blog/2012/10/generating-functions-part1/ )

Your problem would be transformed to the following equivalent problem:

In the formal product of all the factors :
## ( (x^1)^0 + (x^1)^1 + (x^1)^2 + ...)##
##( (x^2)^0 + (x^2)^1 + (x^2)^2 + ...)##
##( (x^5)^0 + (x^5)^1 + (x^5)^2 + ...)##
##( (x^{10})^0 + (x^{10})^1 + (x^{10})^2 + ...)##

what is the coefficient of the term involving ##x^{200}## after all like terms are combined?

It's worth learning about generating functions even if there is a better way to solve your particular problem!
I searched online but I am not sure how to proceed next ?
 
  • #4
Stephen Tashi
Science Advisor
7,175
1,315
I searched online but I am not sure how to proceed next ?
To find the coefficient of ##x^{200}##, it's sufficient to evaluate the product of the finite factors:

## ( (x^1)^0 + (x^1)^1 + (x^1)^2 + ... + (x^1)^{200} )##
##( (x^2)^0 + (x^2)^1 + (x^2)^2 + ...+ (X^2)^{100})##
##( (x^5)^0 + (x^5)^1 + (x^5)^2 + ...+ (x^5)^{40})##
##( (x^{10})^0 + (x^{10})^1 + (x^{10})^2 + ...+ (x^{10})^{20} )##

since using more terms in those factors isn't relevant to contributing to powers of ##x## less than or equal to 200 in the final answer.

A person happy with computer programming or using computer algebra packages would consider the above procedure to be a solution. However, I agree that it would be nice to have a method that gives more insight into the problem. The technique of generating functions is related to the topics of "recursion relations" (e.g. http://www.math.ucsd.edu/~gptesler/184a/slides/184a_ch8slides_f17c-handout.pdf page 12) and "dynamic programming" (e.g.https://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/) . Your line of reasoning involved the topic of "Diophantine equations". If you don't like the generating function approach, you may be able to substitute other methods for it.

(It should be noted that the term "generating function" is used to mean different things in mathematics. The special kind of generating function discussed here is a "combinatorial generating function". )
 
  • #5
StoneTemplePython
Science Advisor
Gold Member
2019 Award
1,158
564
To find the coefficient of ##x^{200}##, it's sufficient to evaluate the product of the finite factors:

## ( (x^1)^0 + (x^1)^1 + (x^1)^2 + ... + (x^1)^{200} )##
##( (x^2)^0 + (x^2)^1 + (x^2)^2 + ...+ (X^2)^{100})##
##( (x^5)^0 + (x^5)^1 + (x^5)^2 + ...+ (x^5)^{40})##
##( (x^{10})^0 + (x^{10})^1 + (x^{10})^2 + ...+ (x^{10})^{20} )##

since using more terms in those factors isn't relevant to contributing to powers of ##x## less than or equal to 200 in the final answer.

A person happy with computer programming or using computer algebra packages would consider the above procedure to be a solution. However, I agree that it would be nice to have a method that gives more insight into the problem.
A nice computational solution would be to write that as the product of 4 finite geometric series i.e. as

##a(x)b(x)c(x)d(x)##
where, for example

##a(x) = \frac{1 - x^{201}}{1 -x}##
and it is understood that ##a(1) = 201##

- - - -
From here either basic polynomial interpolation (via 801 well chosen points on unit circle, i.e. DFT / FFT) will give the answer. Sometimes thinking about the implied distribution associated with these convolutions -- and using a normal approximation can be both insightful and relatively easy.

For a deeper dive, I think OP would benefit from going through these two closely related threads in detail:

https://www.physicsforums.com/threads/how-many-ways-can-you-roll-an-18-from-5-dice.939444/
https://www.physicsforums.com/threads/man-needs-to-buy-cars-combinatorics.941162/

It takes a lot of time to get good at this.
 
Last edited:
  • #6
1,777
139
So it would be like

$$f(x)=1/(1-x)*1/(1-x^2)*1/(1-x^5)*1/(1-x^{10})$$ ?

From here either basic polynomial interpolation (via 201 well chosen points on unit circle, i.e. DFT / FFT) will give the answer. Sometimes thinking about the implied distribution associated with these convolutions -- and using a normal approximation can be both insightful and relatively easy.
I didnt understand this part..This is Idk awkard and strange for me a totaly new subject
 
  • #7
StoneTemplePython
Science Advisor
Gold Member
2019 Award
1,158
564
So it would be like

$$f(x)=1/(1-x)*1/(1-x^2)*1/(1-x^5)*1/(1-x^{10})$$ ?



I didnt understand this part..This is Idk awkard and strange for me a totaly new subject
well kind of, except your series are not in finite series form. If you look into the 2 threads I linked to, you'll see a link to this gem from MIT.

https://ocw.mit.edu/courses/electri...ce-fall-2010/readings/MIT6_042JF10_chap12.pdf

it's part of this course on MIT OCW
https://ocw.mit.edu/courses/electri...j-mathematics-for-computer-science-fall-2010/

maybe you'll want to go through the whole thing. My sense is right now you don't have enough of the background mathematical knowledge to really get a satisfying answer to the problem you're trying to solve. As usual, doing one or two well chosen online MIT courses will fix that :wink:. But they aren't easy!

- - - -

(Btw, you could just set this up as nested for loops / recursion if this is 'merely' a project euler problem.)
 
  • #8
1,777
139
well kind of, except your series are not in finite series form. If you look into the 2 threads I linked to, you'll see a link to this gem from MIT.

https://ocw.mit.edu/courses/electri...ce-fall-2010/readings/MIT6_042JF10_chap12.pdf

it's part of this course on MIT OCW
https://ocw.mit.edu/courses/electri...j-mathematics-for-computer-science-fall-2010/

maybe you'll want to go through the whole thing. My sense is right now you don't have enough of the background mathematical knowledge to really get a satisfying answer to the problem you're trying to solve. As usual, doing one or two well chosen online MIT courses will fix that :wink:. But they aren't easy!

- - - -

(Btw, you could just set this up as nested for loops / recursion if this is 'merely' a project euler problem.)
Yes its a Project Euler question (31). Yes my math is not that good enough we learned in calculus these stuff but not this or not in detail.

I can just create loops as you said but it will have like 8 for loops and Idk how much it will take time to solve it. I can try tho. somewhere I saw sublist subset something like that I am not sure. But let me say that I am not enjoying with this problem...

I looked the links and they are great but I dont think I can learn them or study..it doesnt seem much interesting (its sad I know)
 
  • #9
StoneTemplePython
Science Advisor
Gold Member
2019 Award
1,158
564
Yes its a Project Euler question (31). Yes my math is not that good enough we learned in calculus these stuff but not this or not in detail.I can just create loops as you said but it will have like 8 for loops and Idk how much it will take time to solve it. I can try tho in somewhere I saw sublist subset something like that I am not sure. But let me say that I am not enjoying with this problem...
Haha -- it gets worse with Project Euler the higher the numbering of the problem. You have more patience than I do for the (many) prime number problems on there. But I actually kind of like this problem, and I can think of several interesting ways to solve it.

Off the top of my head, I think, for a brute force recursion you should only need to nest 5 loops. Here's a simple way to estimate the run time. Suppose you iteration from 1 to 200, for each subset -- thats worst case ##200^5## or ##O(N^k)## where you have ##k=5## coin types. Your ##N## is only 200 and k is small so... the result is a big number, but less than ##(1MM)^2## so it could maybe work.

- - - -
Looking back at my solution from the time I did this problem, it appears that I actually set this up as a dynamic programming problem. Interesting -- I mostly reach for dynamic programming when the problem has an obvious optimization feel to it and this one does not so much, though I can see how the subproblems do nicely overlap. The whole thing was pure python and runs in well under a second.

I can't really discuss dynamic programming with you though at this time... you need to have a prior exposure to knapsack problem, etc. to understand what I'm talking about here.

It could be time to take a break and work through some python / intro cs books or online courses. You are getting some exposure to some interesting mathematical and cs ideas though when you look into these problems. (It's just not that gentle of an introduction!)
 
  • #10
1,777
139
Haha -- it gets worse with Project Euler the higher the numbering of the problem. You have more patience than I do for the (many) prime number problems on there. But I actually kind of like this problem, and I can think of several interesting ways to solve it.
Next couple problems are kind of easier then this but yes it definitly does. Is prime number problems harder or something ?

Off the top of my head, I think, for a brute force recursion you should only need to nest 5 loops
Why 5 ?
I wrote something like
Python:
#!/usr/bin/python
import time
start=time.time()
H=[]
for i in range(201):
    for j in range(101):
        for k in range(41):
            for l in range(21):
                for m in range(11):
                    for n in range(5):
                        for p in range(3):
                            for q in range(2):
                                t=i*1+j*2+k*5+l*10+m*20+n*50+p*100+q*200
                                if t==200:
                                    H.append([t,i,j])
end=time.time()
Time=end-start
print(Time)
print(len(H))
Looking back at my solution from the time I did this problem, it appears that I actually set this up as a dynamic programming problem. Interesting -- I mostly reach for dynamic programming when the problem has an obvious optimization feel to it and this one does not so much, though I can see how the subproblems do nicely overlap. The whole thing was pure python and runs in well under a second.

I can't really discuss dynamic programming with you though at this time... you need to have a prior exposure to knapsack problem, etc. to understand what I'm talking about here.
Yes you are right..I dont also think I can understand it. Its nice that it works well with dynamic programming maybe I learn it one day.
It could be time to take a break and work through some python / intro cs books or online courses. You are getting some exposure to some interesting mathematical and cs ideas though when you look into these problems. (It's just not that gentle of an introduction!)
Well from the begining I learned a lot actually..and thats really nice. Also that coding problem that I shared with you it was right. It turns out that my teacher understand me wrong that dt*dt was right..

My fav problems are 7,11 was nice but it was hard, 14,21,23,27 and 35.
 
  • #11
StoneTemplePython
Science Advisor
Gold Member
2019 Award
1,158
564
Next couple problems are kind of easier then this but yes it definitly does. Is prime number problems harder or something ?
I just find the prime number problems to be rather repetitive and dreary for some reason.

Why 5 ?
I wrote something like
Python:
#!/usr/bin/python
import time
start=time.time()
H=[]
for i in range(201):
    for j in range(101):
        for k in range(41):
            for l in range(21):
                for m in range(11):
                    for n in range(5):
                        for p in range(3):
                            for q in range(2):
                                t=i*1+j*2+k*5+l*10+m*20+n*50+p*100+q*200
                                if t==200:
                                    H.append([t,i,j])
end=time.time()
Time=end-start
print(Time)
print(len(H))
I wrote 5 but should have written 4 as you have coin values of 1, 2, 5, and 10. The above looks unpleasant. Spending some time trying to model the problem recursively should be helpful from cleaning up the code and possibly getting some insights into the problems structure.

The brute force idea maybe wouldn't even work -- it's hard to go back to brute force once you have the dynamic programming approach (and a polynomial interpolation approach) in your head.
 
  • #12
1,777
139
I wrote 5 but should have written 4 as you have coin values of 1, 2, 5, and 10.
Yes I agree, I confused when you said that.

he above looks unpleasant. Spending some time trying to model the problem recursively should be helpful from cleaning up the code and possibly getting some insights into the problems structure.
Yes I definitly agree its unpleasant.I think it can solved either dynamic programming or this generating fucntions method.

The brute force idea maybe wouldn't even work -- it's hard to go back to brute force once you have the dynamic programming approach (and a polynomial interpolation approach) in your head.
ıts been an hour and still no answer..It takes quite a long time to solve it (which thats quite normal). I ll just skip this problem but I wonder is there could be a solution rather then the things that I mentioned above
 
  • #13
1,777
139
OMG!!! it solved lol. It took exactly 6170.9934294223785 second which its 102.84989049037297min
I am not proud tho but what can we do right...
 
  • Like
Likes jim mcnamara and StoneTemplePython
  • #14
1,955
252
Dynamic programming is the way to go here. Even if you use generating functions, dynamic pogramming is the fastest way to
compute them anyway. If you implement the last version of the program in the PDF on the projecteuler site,
it will be shorter than your program and use only about 30 microseconds in python. (0.85 microseconds in C).
There will be many more problems where you need this, because brute force won't be ready before the sun burns out.
 

Related Threads on Coin Sum Problem

Replies
21
Views
4K
  • Last Post
Replies
5
Views
3K
  • Last Post
Replies
7
Views
7K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
13
Views
4K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
14
Views
4K
  • Last Post
Replies
19
Views
4K
  • Last Post
Replies
10
Views
3K
  • Last Post
Replies
6
Views
5K
Top