# How many integer solutions are there to $x_1 + x_2 + x_3 + x_4 + x_5 = 31$ with $x_i \leq i$

So i was given this question

How many integer solutions are there to $x_1 + x_2 + x_3 + x_4 + x_5 = 31$ with $x_i \leq i$

So i looked at it and decided i have to use the inclusion exclusion principle for n = 5.

Define 5 sets

$A_i$ = {${(x_1,..., x_5|x1 +...+ x_5 = 31, x_i \geq i+1, x_1,..., x_5 \geq 0}$}

Find sizes of the following subsets:

$A_i, A_i \cap A_j, A_i \cap A_j \cap A_k, A_i \cap A_j \cap A_k \cap A_l, A_1 \cap...\cap A_5$

$i\neq j, i \neq j \neq k, i \neq j \neq k \neq l$

I understand about up to here but i do not know how to proceed to find the answer

• None, because $1 + 2 + 3 + 4 + 5 = 15 < 31$. – user296602 Dec 8 '15 at 0:33
• @Micky, are you quite sure $x_i\le i$ shouldn't be $x_i\ge i$? – vadim123 Dec 8 '15 at 0:35
• @vadim123 question says $x_i \leq i$ – Micky Dec 8 '15 at 0:37
• Then perhaps you mean to ask for "at least one of $x_i$ being less than or equal to $i$" as opposed to $x_i\leq i$ for all $i$ – JMoravitz Dec 8 '15 at 0:38
• @JMoravitz Uhh the way i wrote it is exactly in my book – Micky Dec 8 '15 at 0:45

## 1 Answer

Some possible interpretations I can see:

• How many integer solutions exist to the system $x_1+x_2+x_3+x_4+x_5=31$ such that $x_i\leq i$ for all $i\in \{1,2,\dots,5\}$

There are no solutions since:

$$x_1+x_2+x_3+x_4+x_5\leq 1+2+3+4+5=15<31$$

seen by observing the upper bounds on each of $x_i$ individually.

• How many integer solutions exist to the system $x_1+x_2+x_3+x_4+x_5=31$ exist such that $x_i\leq i$ for some $i\in\{1,2,\dots,5\}$

Notice that $x_1=31, x_2=x_3=x_4=x_5=0$ is a solution and also $x_1=31, x_2=k, x_3=-k, x_4=x_5=0$ is a solution for all values of $k$. This also satisfies the condition that at least one of the $x_i$ is at most $i$ since $x_5=0<5$ in all cases

• How many non-negative integer solutions exist to the system $x_1+x_2+x_3+x_4+x_5=31$ such that at least one of the $x_i$ is bounded above by $i$

Approach via inclusion-exclusion. Letting $A_i$ be the event that $x_i>i$ we are tasked with finding $|U\setminus(A_1^c\cup\dots \cup A_5^c)|=|U|-|A_1\cap\dots \cap A_5|$

To find $|A_1\cap\dots\cap A_5|$, we have the system that: $x_1+\dots+x_5=31$ and $i<x_i$ implying $i+1\leq x_i$. Via a change of variable, setting $y_i = x_i-i-1$, we have $y_1+\dots+y_5=11$. There are then $\left(\!\!\binom{11}{5}\!\!\right)=\binom{11+5-1}{5-1}=\binom{15}{4}$ possible solutions.

Going back to the original problem, there are then $\binom{31+5-1}{5-1}-\binom{11+5-1}{5-1}=\binom{35}{4}-\binom{15}{4}$ total number of solutions.

• How many integer solutions exist to the system $x_1+x_2+x_3+x_4+x_5=31$ such that $x_i\geq i$ for all $i$

Again, approach via a change of variable by setting $y_i=x_i-i$. You have then $\binom{16+5-1}{5-1}=\binom{20}{4}$ total solutions.

• This solution uses the proof-by-cases method. :-) – vadim123 Dec 8 '15 at 1:06