Solve Coin Sum Problem: Find Combinations for 200p

[Arman777]

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 let's 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 don't 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 doesn't 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 ?

 

[Stephen Tashi]

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!

 

[Arman777]

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 ?

 

[Stephen Tashi]

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". )

 

[StoneTemplePython]

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.

 

[Arman777]

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

 

[StoneTemplePython]

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

 

[Arman777]

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 . 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 don't think I can learn them or study..it doesn't seem much interesting (its sad I know)

 

[StoneTemplePython]

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 -- that's 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!)

 

[Arman777]

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 definately 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

#!/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 don't 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 beginning I learned a lot actually..and that's 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.

 

[StoneTemplePython]

Next couple problems are kind of easier then this but yes it definately 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

#!/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.

 

[Arman777]

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 definately agree its unpleasant.I think it can solved either dynamic programming or this generating functions 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 that's 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

 

[Arman777]

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

 

[willem2]

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.