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
  • 5
    $\begingroup$ None, because $1 + 2 + 3 + 4 + 5 = 15 < 31$. $\endgroup$
    – user296602
    Dec 8, 2015 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, 2015 at 0:35
  • $\begingroup$ @vadim123 question says $x_i \leq i$ $\endgroup$
    – Micky
    Dec 8, 2015 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, 2015 at 0:38
  • $\begingroup$ @JMoravitz Uhh the way i wrote it is exactly in my book $\endgroup$
    – Micky
    Dec 8, 2015 at 0:45

1 Answer 1

Reset to default
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, 2015 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.