Solve $x_1+x_2+x_3+x_4+x_5+x_6=20$ such that $x_{2n+1}\leq x_{2n+2}, 0\leq n \leq2$

Edit : I solved it.

Let $0 \le a,b,c \le 20$ such that $0 \le a+b+c \le 20$

$x_1+x_2+x_3+x_4+x_5+x_6=20 \;and\ x_{2n+1}\leq x_{2n+2}\\ \implies x_2=x_1+a,\;x_4=x_3+b,\;x_6=x_5+c\\ \implies 2(x_1+x_2+x_3)+a+b+c=20\\ \implies 2(x_1+x_2+x_3)=20-a-b-c\;\;\;(1)$

So now we need for a fixed values of $a,b,c$ to find the number of non-negative integers solutions to the equation at $(1)$

Now, for all $0 \le i \le 20 $

Let $A_i$ be the set of all non negative solutions for $a+b+c=i$

Let $X_i$ be the set of all non negative solutions for $2(x_1+x_2+x_3)=20-i$


$2(x_1+x_2+x_3)=20-i \implies (x_1+x_2+x_3)= \frac{20-i}{2}$

And since we are interesting in non-negative integers we can say that

$20-i\nmid 2 \implies X_i=\emptyset \implies |X_i|=0\;\;\;(2)$


If $i$ is even we will want to compute

$\left|A_i\right|\cdot \left|X_i\right|$ because for any solution a+b+c=i in $A_i$ there's the corresponding solution in $X_i$

Therefore we have:

$\sum _{i=0}^{20}\:\left(\left|A_i\right|\cdot \left|X_i\right|\right)=\sum _{i=0}^{20}\:\begin{pmatrix}i+3-1\\ \:i\end{pmatrix}\begin{pmatrix}10-i+3-1\\ \:10-1\end{pmatrix}\\ \text{and from (2)}\\\sum _{i=0}^{20}\:\begin{pmatrix}i+3-1\\ \:i\end{pmatrix}\begin{pmatrix}10-i+3-1\\ \:10-1\end{pmatrix}= \sum \:_{i=0}^{10}\:\begin{pmatrix}2i+3-1\\ \:\:2i\end{pmatrix}\begin{pmatrix}10-i+3-1\\ \:\:10-i\end{pmatrix}=\\ \sum _{i=0}^{10}\:\left(\frac{\left(2i+2\right)\left(2i+1\right)}{2}\right)\left(\frac{\left(12-i\right)\left(11-i\right)}{2}\right)=9009$

And we've got a palindrome.

  • $\begingroup$ The line with a factor of $2$ outside the parentheses is incorrect. You should have $2(x_1 + x_2 + x_3) + a + b + c = 20$. $\endgroup$ – N. F. Taussig Sep 20 '17 at 12:04
  • $\begingroup$ Are we interested in solving the problem in the positive integers or the nonnegative integers? $\endgroup$ – N. F. Taussig Sep 20 '17 at 12:11
  • $\begingroup$ Also, your title could be interpreted differently than the statement "Solve $x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 20$ such that $x_{2n + 1} \leq x_{2n + 2}, 0 \leq n \leq 2$." $\endgroup$ – N. F. Taussig Sep 20 '17 at 12:14
  • $\begingroup$ Non-negative integers $\endgroup$ – idan di Sep 20 '17 at 13:26
  • $\begingroup$ @N.F.Taussig thanks I fixed everything $\endgroup$ – idan di Sep 20 '17 at 14:20

I verified your solution a different way:

Let $N(i)$ denote the number of ways to have $x_{1}+x_{2}=i$ with $x_{1}\leq x_{2}$. It is easy to show that $N(i)=\lfloor\frac{i}{2}\rfloor+1$, for $0\leq i$.

Your problem now reduces to computing the following sum:

$\sum_{(k_{1},k_{2},k_{3})\in K}N(k_{1})\cdot N(k_{2})\cdot N(k_{3})$

where $K=\{(k_{1},k_{2},k_{3}):k_{1}+k_{2}+k_{3}=20,\ k_{i}\geq 0\}$, i.e. the set of ordered pairs of three non-negative integers summing to 20.

After a bit of sum-manipulating we get the equivalent sum:

$\sum_{k_{1}=0}^{20}N(k_{1})\sum_{k_{2}=0}^{20-k_{1}}N(k_{2})\cdot N(20-(k_{1}+k_{2}))$

Now throw elegance to the curb, enter the sum into Mathematica, and get 9009 $\checkmark$.

  • $\begingroup$ You wrote that K_i greater then zero But why not to say that there's at least one K_i greater then zero ? Not All K_i must be greater then zero. If I understood $\endgroup$ – idan di Sep 20 '17 at 23:09
  • $\begingroup$ @idandi That was my mistake, I meand $k_i \geq 0$. I edited the post to reflect the change. $\endgroup$ – mm8511 Sep 20 '17 at 23:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.