A balloon artist is hosting a show with 7 kids. He bought 8 yellow balloons, 8 red balloons, 5 blue balloons. If he wants to give 16 balloons in total for the kids, so each gets two balloons, and including at least 2 yellow balloons, and 1 red balloon.
Use the inclusion-exclusion principle to find the possibilities to choose from the balloons he bought. Not distinguishing between who gets what balloon, only considering the 16 balloons.
How would the inclusion-exclusion principle work on this question? I can't seem to find a reasonable answer.
here is what i tried:
$\binom{21}{16}$ is the total ways to choose from all types of balloons.
$\binom{18}{16}$ number of ways with at most 3 yellow,
$\binom{20}{16}$number of ways with at most $1$ red.
$\binom{21}{16}-\binom{18}{16}-\binom{20}{16}$
But i don't think that's quite right.
Best Answer
Let $b$, $r$, and $y$ denote, respectively, the number of blue, red, and yellow balloons. Since the artist wishes to distribute $16$ balloons, $$b + r + y = 16 \tag{1}$$ Since there are only five blue, eight red, and eight yellow balloons available, $b \leq 5$, $r \leq 8$, and $y \leq 8$. Moreover, since at least one red balloon and at least two yellow balloons must be included, $r \geq 1$ and $y \geq 2$.
Place one red and two yellow balloons in the collection. Then we have $13$ additional balloons to distribute. Let $r' = r - 1$ be the number of red balloons remaining; let $y' = y - 2$ be the number of yellow balloons remaining. Then $$b + r' + g' = 13 \tag{2}$$ You can check this is correct by substituting $r' + 1$ for $r$ and $y' + 2$ for $y$ in equation 1, then simplifying. Notice that $r \leq 8 \implies r' \leq 7$ and $y \leq 8 \implies y' \leq 6$. Hence, we wish to find the number of solutions of equation 2 subject to the restrictions that $b \leq 5$, $r' \leq 7$, and $y' \leq 6$.
Equation 2 is an equation in the nonnegative integers. A particular solution of equation 2 in the nonnegative integers corresponds to the placement of two addition signs in a row of $13$ ones. For instance, $$1 1 1 1 + 1 1 1 1 1 + 1 1 1 1$$ corresponds to the solution $b = 4$, $r = 5$, $y = 4$, while $$1 1 1 1 1 1 1 + 1 1 1 1 1 1$$ corresponds to the solution $b = 7$, $r = 6$, $y = 0$ (which violates our restrictions). If we ignore our restrictions for the moment, the number of solutions of equation 2 in the nonnegative integers is the number of ways we can place two addition signs in a row of $13$ ones, which is $$\binom{13 + 3 - 1}{3 - 1} = \binom{15}{2}$$ since we must choose which $3 - 1 = 2$ ($3$ corresponds to the number of variables) of the $13 + 3 - 1$ positions required for $13$ ones and $3 - 1 = 2$ addition signs will be filled with addition signs.
From these solutions, we must subtract those that violate one or more of the above restrictions. Notice that at most two of the restrictions can be violated simultaneously since $6 + 8 + 7 = 21 > 13$. In fact, it is not possible to simultaneously violate the restrictions that $r' \leq 7$ and $y' \leq 6$ since $8 + 7 = 15$ or to simultaneously violate the restrictions that $b \leq 5$ and $r' \leq 7$ since $6 + 8 = 14 > 13$. It is possible to simultaneously violate the restrictions that $b \leq 5$ and $y' \leq 6$ since $6 + 7 = 13$.
Let $B$ be the event that $b > 5$; let $R$ the event that $r' > 7$ (or, equivalently, that $r > 8$); let $Y$ be the event that $y' > 6$ (or, equivalently, that $y > 8$).
$|B|$: Suppose $b > 5$. Then $b' = b - 6$ is a nonnegative integer. Substituting $b' + 6$ for $b$ in equation 2 and simplifying yields $$b' + r' + y' = 7 \tag{3}$$ which is an equation in the nonnegative integers.
$|R|$: Suppose $r' > 7$. Then $r'' = r' - 8$ is a nonnegative integer. Substituting $r'' + 8$ for $r'$ in equation 2 and simplifying yields $$b + r'' + y' = 5 \tag{4}$$ Equation 4 is an equation in the nonnegative integers. How many solutions does it have?
$|Y|$: Suppose $y' > 6$. Then $y'' = y' - 7$ is a nonnegative integer. Substituting $y'' + 7$ for $y'$ in equation 2 and simplifying yields $$b + r' + y'' = 6 \tag{5}$$ Equation 5 is an equation in the nonnegative integers. How many solutions does it have?
If we subtract the number of solutions of equations 3, 4, and 5 from the total, we will have subtracted too much since we will have subtracted the number of solutions that simultaneously violate the restrictions $b \leq 5$ and $y' \leq 6$ twice, once when we subtract those solutions which violate the restriction $b \leq 5$ and once when we subtract those solutions which violate the restriction $y' \leq 6$. We only want to subtract those solutions once. Therefore, we must add them back.
$|B \cap Y|$: If $b > 5$ and $y' > 6$, then $b' = b - 6$ and $y'' = y' - 7$ are nonnegative integers. Substituting $b' + 6$ for $b$ and $y'' + 7$ for $y'$ in equation 2 and simplifying yields $$b' + r' + y'' = 0$$ which only has one solution in the nonnegative integers.
By the Inclusion-Exclusion Principle, the number of ways a collection of $16$ balloons can be obtained from five blue, eight red, and eight yellow balloons if at least one red and at least two yellow balloons are in the collection is $$\binom{15}{2} - |B \cup R \cup Y|$$ where $$|B \cup R \cup Y| = |B| + |R| + |Y| - |B \cap R| - |B \cap Y| - |R \cap Y| + |B \cap R \cap Y|$$ Can you fill in the missing details?