Generating function?

Computer Science Level pending

Let $a,b,c$ and $d$ be non-negative integers satisfying $a+b+c+d=360$ , and that $b,c,d$ are multiplies of 2, 3, 5, respectively.

Let $P$ denote the total number of solutions satisfying the condition above, and
$Q$ denote the total number of solutions satisfying the condition above with an additional constraint of $a= 0$ .

Find the sum of the first 7 digits of $\dfrac QP$ after the decimal point.

I did label this question as computer science because I did it that way. If anyone know how to solve it with generating function, please help.

8.194E-2 22 24 26 25 23

1 solution

Akira Kato
Jul 12, 2016

int tcount=0, acount=0;
    double prob=0;

    for(int a=0; a<361;a++){
        for(int b=0; b<361; b=b+2){
            for(int c=0;c<361;c=c+3){
                for(int d=0; d<361;d=d+5){
                    if(a+b+c+d==360){
                        tcount++;
                        if(a==0)
                            acount++;
                        }

                    }
                }
            }
        }
    prob=((double)acount/(double)tcount);

Yes, there's a technique to determine the exact probability of $\dfrac{2221}{271243}$ , but the working gets very tedious.

First, your question simplifies to $2B + 3C + 5D = 360$ . So we want to find the value of coefficient of $x^{360}$ in the Maclaurin series of $\dfrac1{(1-x^2)(1-x^3)(1-x^5)}$ . And it turns out that it's 2221.

Next, we find the total number of non-negative integer triplets $(B,C,D)$ satisfying the given equation $2B + 3C + 5D = 360$ . By using linear Diophantine equations techniques , in particular, by applying the Bezout's Identity . And this comes out to be 271243.

Take their ratio and you get your answer.

Pi Han Goh - 4 years, 11 months ago

Amazing. I need to spend some time digesting this. Btw, did you compute the coefficient of X^360 using a software.

Akira Kato - 4 years, 11 months ago

Yes. Otherwise, it gets super duper tedious. Your question is best left for a computer to solve, or for someone who has nothing else better to do.

Pi Han Goh - 4 years, 11 months ago

Generating function?

I did label this question as computer science because I did it that way. If anyone know how to solve it with generating function, please help.

1 solution

0 pending reports