Post by: Momo.05 on February 13, 2010, 09:06:28 pm
can someone help me solve this? Please. Thanks. :)
Post by: TrueTears on February 13, 2010, 11:25:46 pm
We need to find how many distinct
Let
We need to find
Define
Now
Thus
Our aim is the find the coefficient of the
Post by: QuantumJG on February 14, 2010, 12:42:51 am
We need to find how many distinctthere are.
Letbe the number of nonnegative ordered 4-tuple
We need to find
Define
NowB(x)C(x)D(x) = (1+x^{30}+x^{60} + \cdots)(1+x^{20}+x^{40} + \cdots)(1+x^{15}+x^{30} + \cdots)(1+x^{12}+x^{24} + \cdots) = 1+x^{12}+x^{15}+x^{20} + x^{24} + \cdots)
Thusand so on.
Our aim is the find the coefficient of theterm, which looks like a recurrence relation.
I'm confused with that A(x),B(x)... notation. :S
Post by: TrueTears on February 14, 2010, 12:43:13 am
Post by: QuantumJG on February 14, 2010, 12:53:13 am
- A(x) = x0(30) + x1(30) + x2(30) + x3(30) ...
It's generating functions but I don't know how these relate to the problem.
Post by: kamil9876 on February 14, 2010, 12:57:03 am
We have:
150a+100b+75c+60d=1000
And now we will keep reducing this equation:
30a+20b+15c+12d=200
From here on we see that c must be even and d must be a multiple of 5, hence let c=2k, d=5x:
30a+20b+30k+60x=200
3a+2b+3k+6x=20
Now we can see that b cannot be a multiple of 3, hence b is of the form b=3m+1 or b=3m+2 (mutually exclusive cases). By plugging in the second case we get:
3a+2(3m+2)+3k+6x=20
3a+6m+3k+6x=16
3(a+2m+k+2x)=16 which implies 16 has 3 as a factor, a contradiction. Hence only the first case is possible:
3a+2(3m+1)+3k+6x=20
3a+6m+3k+6x=18
a+2n+k+2x=6
And now find how many different solutions there are to that equation. Which is done manually or by computer or maybe generating functions (dunno what is quickest so far).
Post by: TrueTears on February 14, 2010, 12:59:06 am
So,
- A(x) = x0(30) + x1(30) + x2(30) + x3(30) ...
It's generating functions but I don't know how these relate to the problem.
Ahmad taught me alot about generating functions (eg, http://vcenotes.com/forum/index.php/topic,19896.msg210235.html#msg210235), you could also have a read in AnC's page 136
Post by: TrueTears on February 14, 2010, 01:00:35 am
Hi. Let a,b,c,d be the number of 150,100,75,60 wat bulbs used respsectively.wait how did you get 30a+20b+3c+12d=200?
We have:
150a+100b+75c+60d=1000
And now we will keep reducing this equation:
30a+20b+3c+12d=200
From here on we see that c must be even, hence let c=2k:
30a+20b+6k+12d=200
15a+10b+2k+6d=100
From here on, we see that a must be even, hence let a=2m:
30m+10b+2k+6d=100
15m+5b+k+3d=50
So we wanna know the numbers of non-negative integer solutions to that equation.
This sort of simplifies the problem to smaller numbers, but doesn't simplify it as much as I hoped. To proceed further you can use a similair approach as TT did with the generating functions.
letinstead of 50. We want to know
.
Now you just multiply it out and equate coefficients etc. and you get some more equations that solve it. I'm too tired to proceed further but I don't know how much it simplifies the problem too, I have the pessimistic feeling that it can't probably be simplified to the point that we don't need to do a fairly large amount of tedious listing.
Post by: kamil9876 on February 14, 2010, 01:02:53 am
Post by: TrueTears on February 14, 2010, 01:04:41 am
ahh yes sorry, 75/5=15. lol ill edit nowlol yeah, the other steps follow on.
Post by: kamil9876 on February 14, 2010, 01:19:37 am
ahh yes sorry, 75/5=15. lol ill edit now
wow, noticing that blunder led to a better simplification, check out new edited post :)
Post by: QuantumJG on February 14, 2010, 01:36:41 am
ahh yes sorry, 75/5=15. lol ill edit now
wow, noticing that blunder led to a better simplification, check out new edited post :)
Do we learn how to do this at uni?
Post by: TrueTears on February 14, 2010, 01:46:44 am
wow much better, yeah now generating functions work better...ahh yes sorry, 75/5=15. lol ill edit now
wow, noticing that blunder led to a better simplification, check out new edited post :)
Post by: TrueTears on February 14, 2010, 01:47:38 am
You can have a read of H.S.Wilf, Generating Functionalogy.ahh yes sorry, 75/5=15. lol ill edit now
wow, noticing that blunder led to a better simplification, check out new edited post :)
Do we learn how to do this at uni?
Post by: QuantumJG on February 14, 2010, 01:48:38 am
wow much better, yeah now generating functions work better...ahh yes sorry, 75/5=15. lol ill edit now
wow, noticing that blunder led to a better simplification, check out new edited post :)
Could someone tell me the basics of how you generate functions?
Post by: kamil9876 on February 14, 2010, 12:07:29 pm
Hi. Let a,b,c,d be the number of 150,100,75,60 wat bulbs used respsectively.
We have:
150a+100b+75c+60d=1000
And now we will keep reducing this equation:
30a+20b+15c+12d=200
From here on we see that c must be even and d must be a multiple of 5, hence let c=2k, d=5x:
30a+20b+30k+60x=200
3a+2b+3k+6x=20
Now we can see that b cannot be a multiple of 3, hence b is of the form b=3m+1 or b=3m+2 (mutually exclusive cases). By plugging in the second case we get:
3a+2(3m+2)+3k+6x=20
3a+6m+3k+6x=16
3(a+2m+k+2x)=16 which implies 16 has 3 as a factor, a contradiction. Hence only the first case is possible:
3a+2(3m+1)+3k+6x=20
3a+6m+3k+6x=18
a+2n+k+2x=6
And now find how many different solutions there are to that equation. Which is done manually or by computer or maybe generating functions (dunno what is quickest so far).
Now to finish it off:
(a+k)+2(n+x)=6
We have four cases:
a+k=0, 2(n+x)=6. 1 way to get a+k=0, 4 ways to get n+x=3
a+k=2, 2(n+x)=4. 3 ways to get a+k=2, 3 ways to get n+x=2
a+k=4, 2(n+x)=2. 5 ways to get a+k=4, 2 ways to get n+x=1
a+k=6, 2(n+x)=0. 7 ways to get a+k=6, 1 way to get n+x=0
Hence the final answer
Post by: Momo.05 on February 14, 2010, 12:08:26 pm
Post by: kamil9876 on February 14, 2010, 12:17:08 pm
wow much better, yeah now generating functions work better...ahh yes sorry, 75/5=15. lol ill edit now
wow, noticing that blunder led to a better simplification, check out new edited post :)
Could someone tell me the basics of how you generate functions?
You don't really "generate functions". It's more like a function whose only purpose is to encode information in the coefficients etc. For example:
encodes information about
Or you can differentiate it and set x=1 to get another fancy identity:
So generating functions allow you to do combinatorics without actually doing much thinking, but mostly algebraic manipulation. Of course there are more interesting examples of how generating functions can be used to derive all sorts of deep facts with minimal effort. A favourite of mine that converted me to and convinced me of the power of generatingfunctionology is the application of it to Partitions of an integer.
Post by: Ahmad on February 14, 2010, 01:29:01 pm
Post by: kamil9876 on February 14, 2010, 01:57:53 pm
Post by: the.watchman on February 14, 2010, 01:59:28 pm
gtfo! Elementary/Erdosian/pigeonhole principle type arguments FTW
LOL, everyone loves pigeonhole principle!!! :D
Post by: TrueTears on February 14, 2010, 02:08:01 pm
Generating functions :smitten:mmm and you passed the love to me