9
$\begingroup$

Problem:
Let $x_1$, $x_2$ and $x_3$ be integers such that $x_1 \geq 0$, $x_2 \geq 0$ and $x_3 \geq 0$. How many solutions does the following equation have: $$ x_1 + 2x_2 + 2x_3 = 200 $$

Answer:
Let $c$ be the number of solutions of this equation. For the case where $x_1$ is odd, the equation has no solutions. Now I consider the smallest case of $x_1$ where $x_1 = 0$. I now have the following equation: $$2x_2 + 2x_3 = 200 $$ or $$ x_2 + x_3 = 100 $$ This equation has $101$ solutions. Now I consider the case where $x_0 = 2$. I now have the following equation: $$2 + 2x_2 + 2x_3 = 200 $$ or $$ x_2 + x_3 = 99 $$ This equation has $100$ solutions. Now I consider the case where $x_0 = 4$. I now have the following equation: $$4 + 2x_2 + 2x_3 = 200 $$ or $$ x_2 + x_3 = 98 $$ This equation has $99$ solutions. Now I consider the case where $x_0 = 200$. I now have the following equation: $$100 + 2x_2 + 2x_3 = 200 $$ or $$ x_2 + x_3 = 0 $$ This equation only has one solution.

\begin{align*} c &= \sum_{i = 0}^{100} i+1 = \sum_{i = 1}^{100} i + \sum_{i = 0}^{100} 1 \\ \sum_{i = 1}^{100} i &= \dfrac{ 100(101) }{2} = 50(101) \\ \sum_{i = 0}^{100} 1 &= 101 \\ c &= 50(101) + 101 \\ c &= 5151 \end{align*}

Is my solution correct?

$\endgroup$

2 Answers 2

12
$\begingroup$

Your solution seems correct, but a quicker way would be the following:

As you observed, $x_1$ has to be even, so the problem will have as many solutions as the number of solutions to the problem of

$$2x_1+2x_2+2x_3=200,$$

i.e.

$$x_1+x_2+x_3=100.$$

Now this problem is the same problem as the number of ways to split $100$ objects into $3$ containers, which can also be considered as the number of words with $100$ of one letter, and $2$ of another (think of the $100$ letters as your objects and the $2$ letters as sectioning them off into the containers). This problem is simple and gives you the number as

$$\frac{102!}{100!\cdot 2!}=\frac{101\cdot 102}{2}=101\cdot 51=5151.$$

$\endgroup$
1
  • 7
    $\begingroup$ This is a nice solution. For clarity, however, I would suggest replacing $x_1$ with $2t$ (i.e., use some variable other than $x_1$). $\endgroup$
    – paw88789
    Mar 15, 2022 at 22:02
1
$\begingroup$

I do not know whether you are interested in a little bit advance but much more easier technique which is generating functions.Nonetheless , i thought that this may help you to get rid of long techniques and expand your vision over combinatorics problems. Anyway , here is my solution for you :

You say that $x_1 \geq0 ,x_2 \geq 0 , x_3\geq 0$ , so

  • Possible values for $x_1: 0,1,2,3,4,5,6,....$

  • Possible values for $x_2: 0,1,2,3,4,5,6,....$ . Then , the possible values for $2x_2=0,2,4,6,8,....$

  • Possible values for $x_3: 0,1,2,3,4,5,6,....$ . Then , the possible values for $2x_3=0,2,4,6,8,....$

Now , write the generating functions ,which are polynomial series whose exponents satisfy the values that the variables can take, for each variable $x_1,x_2,x_3$ such that

  • For $x_1:$ $$\frac{1}{1-x}=x^0+x^1+x^2+x^3 +x^4 +....$$

  • For $2x_2:$ $$\frac{1}{1-x^2}=x^0+x^2+x^4+x^6 +x^8 +....$$

  • For $2x_3:$ $$\frac{1}{1-x^2}=x^0+x^2+x^4+x^6 +x^8 +....$$

Now , if we find the product of these three series , we find a PRODUCT such that the product has exponent ,as well. Then ,the coefficient of the $\color{blue}{x}$ whose exponent is equal to $\color{red}{200}$ will give you the number of possible solutions satisfying $x_1+x_2+x_3=200$

$\therefore$ the answer is $5151$

$\mathbf{\text{EDITION}:}$ Calculation of result without using Wolfram-Alpha:

We need to find $$[x^{200}]\bigg(\frac{1}{1-x}\bigg)\bigg(\frac{1}{1-x^2}\bigg)^2$$

When you see generating function forms , $[x^k]$ means that we are looking for the coefficient of the term of $x^k$. Now , lets remember binomial expansion a little bit.

  • The coefficient of the term $x^k$ in the expansion of $(\frac{1}{1-x})$ is equal to $\binom{k+\color{red}{1}-1}{k}$ where the red one represent the exponential of the $(\frac{1}{1-x})$ , so any term in this expansion is equal to $\binom{k+\color{red}{1}-1}{k}x^k$

  • The coefficient of the term in the expansion of $(\frac{1}{1-x^2})^2$ is equal to $\binom{m+\color{red}{2}-1}{k}$ where the red two represent the exponential of the $(\frac{1}{1-x^2})^{\color{red}{2}}$ , so any term in this expansion is equal to $\binom{m+\color{red}{2}-1}{m}(x^2)^m$

In this expansion we look for $2m+k=200$ where

  • $m \in \{100,99,98,...,2,1,0\}$

  • $k \in \{0,2,4,..,196,198,200\}$

As you see the matching , for example , when $m=100$ then $n=0$ and when $m=99$ then $n=2$ so on. Then we need to find the summation of the coefficient of those cases such that

  • When $m=100$ and $n=0$ , then the coefficient of $x^{200}= \binom{100+2-1}{100}\binom{0+1-1}{0}$

  • When $m=99$ and $n=2$ , then the coefficient of $x^{200}= \binom{99+2-1}{99}\binom{2+1-1}{2}$

  • When $m=0$ and $n=200$ , then the coefficient of $x^{200}= \binom{0+2-1}{0}\binom{200+1-1}{200}$

As you see , it is equal to $$101+100+...+1 = \frac{101 \times 102}{2}=5151$$

As you see my dear friend @trueblueanil , calculation of them without using software is not enjoyable in some cases..

$\endgroup$
7
  • $\begingroup$ How do you actually get the value when Wolfram doesn't expand fully ? $\endgroup$ Mar 22, 2022 at 7:18
  • $\begingroup$ @trueblueanil when you do not use wolfram , generally expanded binomial theorem is used for expansion.However , it is very long process for some types of questions. I am putting here some of my answer which i get in calculation . Link 1,,,,Link 2-) $\endgroup$ Mar 22, 2022 at 8:12
  • $\begingroup$ @trueblueanil i wll edit the answer for you , wait please $\endgroup$ Mar 22, 2022 at 8:26
  • 1
    $\begingroup$ Thanks for the added explanation. Yes, sometimes g.f's are easy to write down as an approach, but difficult to compute ! :-) $\endgroup$ Mar 22, 2022 at 8:57
  • 1
    $\begingroup$ For the lucid added material, (+1) ! $\endgroup$ Mar 22, 2022 at 16:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .