Determine how many integer solutions to the inequality $x_1+x_2+...+x_5\lt 110$

175 Views Asked by At

where $3\lt x_i\le 29, i=1,2$ and $10\le x_j\le 40, j=3,4.$

my work:

$x_1+x_2+...+x_6=110$ where $0\lt x_i-3\le 26, i=1,2$ and $1\le x_j-9\le 31, j=3,4$ and $0\lt x_6$

The number of solutions of the Eq. is the same as the number of the nonnegative integer solution of

$y_1+y_2+...+y_6=110-[3+3+9+9+1]=85$ where $0\lt y_i=x_i-3\le 26, i=1,2$ and $0\lt y_j=x_j-9\le 31, j=3,4$ and $0\lt y_6$

now I know that I have to get the total number of solutions and exclude the cases where $y_1,y_2\gt 26$ and $y_3,y_4\gt31 $

and this is the problem. I don't know how to do it. it's not like I'll keep assuming every case, so is there an effective way to do this.

1

There are 1 best solutions below

12
On BEST ANSWER

This can be done with generating functions, as suggested by JMoravitz in a comment, and it's quite possible to do it with a pencil, though you'll probably want to use a calculator to do the arithmetic; I certainly did.

First, to understand the comment, note that $x_1$ and $x_2$ are each represented by the polynomial $$x^4+x^5+x^6+\dots+x^{29}.$$ This is because $4\leq x_1,x_2\leq29$. Similarly, $x_3$ and $x_4$ are each represented by the polynomial $$x^{10}+x^{11}+\dots+x^{40}.$$ Finally, $x_5$ and $x_6$ are each represented by the polynomial $$1+x+x^2+\dots+x^{109}$$ Since the sum is to be $109$, neither $x_5$ nor $x_6$ can be more than $109$, and they must be $\geq0$.

To multiply these $6$ polynomials, we choose a term from each polynomial, multiply them together, and add up the products over all choices of terms. The coefficients in the polynomials are all $1$, so the coefficient of $x^n$ in the product, for some natural number $n$, is just the number of ways to pick one term from each polynomial such that the sum of their exponents is $n$. When $n=109$, this is just the solution to our problem. For example, the solution $x_=20,x_2=14,x_3=30,x_4=30,x_5=15,x_6=0$ corresponds to choosing the terms $x^{20},x^{14},x^{30},x^{30},x^{15},1$ from the polynomials, in order.

Now it's just a matter of figuring out the coefficient of $x^{109}$ without multiplying the polynomials.

I'll use the notation $[x^n]p(x)$ to mean the coefficient of $x^n$ in the formal power series $p(x)$. We want $$c=[x^{109}]\left(x^4+\cdots+x^{29}\right)^2 \left(x^{10}+\cdots+x^{40}\right)^2 \left(1+x+x^2+\cdots\right)^2 $$ Note that we don't need an upper bound on the $x_5$ and $x_6$. It doesn't matter if we include exponents $>109$ in the polynomial, because they won't contribute anything to the coefficient of $x^{109}$ in the product. As you'll see, this simplifies the calculation, because we have two fewer factor of the numerator this way.

Then, using the formula for a geometric series,$$ \begin{align} c&=[x^{109}]\left(x^4-x^{30}\right)^2 \left(x^{10}-x^{41}\right)^2(1-x)^{-6}\\ &=[x^{81}]\left(1-x^{26}\right)^2 \left(1-x^{31}\right)^2 \sum_{n=0}^\infty\binom{-6}{n}(-x)^n\\ &=[x^{81}](1-2x^{26}+x^{52})(1-2x^{31}+x^{62}) \sum_{n=0}^{81}(-1)^n\binom{n+5}{5}(-x)^n\\ &=[x^{81}](1-2x^{26}-2x^{31}+x^{52}+4x^{57}+x^{62}) \sum_{n=0}^{81}\binom{n+5}{5}x^n\\ \end{align}$$
since we may ignore terms of degree $>81$.

We just need to pick out the terms in the product that result in a term of degree $81.$ We have $$ \binom{86}{5}-2\binom{60}5-2\binom{55}5+\binom{34}5+4\binom{29}5+\binom{24}5=17,741,536 $$