0
$\begingroup$

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

$\endgroup$
5
  • 4
    $\begingroup$ None, because $1 + 2 + 3 + 4 + 5 = 15 < 31$. $\endgroup$ – user296602 Dec 8 '15 at 0:33
  • 1
    $\begingroup$ @Micky, are you quite sure $x_i\le i$ shouldn't be $x_i\ge i$? $\endgroup$ – vadim123 Dec 8 '15 at 0:35
  • $\begingroup$ @vadim123 question says $x_i \leq i$ $\endgroup$ – Micky Dec 8 '15 at 0:37
  • 1
    $\begingroup$ 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$ $\endgroup$ – JMoravitz Dec 8 '15 at 0:38
  • $\begingroup$ @JMoravitz Uhh the way i wrote it is exactly in my book $\endgroup$ – Micky Dec 8 '15 at 0:45
1
$\begingroup$

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.

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

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.