1
$\begingroup$

Today I came across the inclusion-exclusion principle for the first time. I believe I have understood it, however when I tried solving some questions on it, I got severely stuck. I couldn't solve any of them. Could you please suggest some questions of escalating difficulty, so that I can get a good grasp on the topic at hand? One of the questions is this one :inclusion-exclusion problem - sitting arrangement , It was in a Greek contest-math book and I also found it on this site.

The other question I couldn't find it on the internet, so I'll translate it:

Find the number of solutions to the equation $x_1+x_2+x_3=100$, if for every $3\ge i\ge1$, xi is a non negative integer with $40\ge x_i$.

I have found the solutions to both of these questions, the reason which I am posting them as well, is to give a better understanding to the reader of the post (as pointed out in the comments), of what level of questions in inclusion-exclusion principle are giving me difficulty

$\endgroup$
4
  • 1
    $\begingroup$ Maybe it would be better if you would post the questions you did not succeed to solve, so we can see what kind of difficulties you have. $\endgroup$ – TheSilverDoe Aug 16 '20 at 16:47
  • $\begingroup$ ok sure, I'll post some links to those which already exist in English, and I'll translate the others $\endgroup$ – user814992 Aug 16 '20 at 16:49
  • $\begingroup$ within 5 minutes I'll have edited the post $\endgroup$ – user814992 Aug 16 '20 at 16:49
  • 3
    $\begingroup$ The art of problem solving usually has good problems. $\endgroup$ – lulu Aug 16 '20 at 16:49
1
$\begingroup$

The second, translated, question doesn't really need inclusion-exclusion; it's quite easily done using stars and bars, which is another technique well worth learning (if you haven't already done so):

Let's write $u_i=40-x_i$, so that the restriction is $u_i\ge0$, and then rewrite the equation to solve as

$$u_1+u_2+u_3=20$$

(This comes from $100=x_1+x_2+x_3=(40-u_1)+(40-u_2)+(40-u_3)=120-(u_1+u_2+u_3)$, and then moving stuff around.) Stars and bars now says the number of non-negative triples summing to $20$ is

$${22\choose2}={22\cdot21\over2}=231$$

To be honest, I think I'd have a hard time solving this problem using inclusion-exclusion; I'd be interested myself in seeing if there's an easy way to do so.

$\endgroup$
1
  • $\begingroup$ I added an inclusion-exclusion solution just now. $\endgroup$ – RobPratt Aug 23 '20 at 21:32
1
$\begingroup$

Here's the inclusion-exclusion approach for the second problem, where $k$ is the number of $i\in\{1,2,3\}$ with $x_i \ge 41$: \begin{align} \sum_{k=0}^2 (-1)^k \binom{3}{k} \binom{100-41k+3-1}{3-1}&=\binom{102}{2}-3\binom{61}{2}+3\binom{20}{2}\\&=5151-3 \cdot 1830+3 \cdot 190\\&=\color{red}{231}. \end{align} The $$\binom{100-41k+3-1}{3-1}$$ part comes from a stars-and-bars count of the nonnegative integer solutions to $x_1+x_2+x_3=100$ with $x_i \ge 41$ for $k$ specified $i\in\{1,2,3\}$, equivalently, the nonnegative integer solutions to $y_1+y_2+y_3=100-41k$.

$\endgroup$

Your Answer

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