Skip to main content

Chapter 18 Inclusion/Exclusion

Exercises Practice Problems

1. Rolling 10 Dice.

We roll 6-sided die 10 times, and then list the outcomes in order as \((x_1, x_2, \ldots , x_{10} )\text{.}\) We are interested in counting the total number outcomes in which both 1 appears and 2 appears. We break this process into multiple steps.

  1. Let \(X\) be the set of all possible outcomes \((x_1, x_2, \ldots , x_{10} )\text{.}\) What is \(|X|\text{?}\) Solution.

    For each \(x_i\text{,}\) we have 6 possible rolls. By the product principle, the answer is

    \begin{equation*} |X| = 6^{10} \end{equation*}

  2. Let \(X_1\) be the set of outcomes that do not contain any 1's. I would call \(X_1\) the set of "bad outcomes for 1." What is \(|X_1|\text{?}\) Solution.

    For each \(x_i\text{,}\) we have 5 possible rolls since rolling a 1 is forbidden. By the product principle, the answer is

    \begin{equation*} |X_1| = 5^{10} \end{equation*}

  3. Define \(X_2\) in the same way as in part (b), where \(X_2\) is the set of "bad outcomes for 2." What is \(|X_2|\text{?}\) Solution.

    As in the previous problem the answer is

    \begin{equation*} |X_2| = 5^{10} \end{equation*}

  4. How many outcomes are there in which neither 1 or 2 appears? How would you describe this set using the symbols \(X_1\) and \(X_2\text{?}\) Solution.

    The set described is \(X_1 \cap X_2\text{.}\) This time, there are 4 numbers allowed for each role, so

    \begin{equation*} |X_1 \cap X_2| = 4^{10} \end{equation*}

  5. Use inclusion-exclusion to find the number of outcomes in which either 1 does not or appear or 2 does not appear (or both do not appear). This account for all the "bad outcomes." Solution.

    \begin{equation*} |X_1 \cup X_2 | = |X_1| + | X_2| - |X_1 \cap X_2| = 5^{10} + 5^{10} - 4^{10} \end{equation*}

  6. Now use your answer from part (d) to find the number of "good outcomes." Namely, how many outcomes contain both 1 and 2? Solution.

    \begin{equation*} 6^{10} - \left( 5^{10} + 5^{10} - 4^{10} \right) = 6^{10} - 2 \cdot 5^{10} + 4^{10} \end{equation*}

2. I Hate 2, 5, and 7.

In this question, you will determine how many numbers between 1 and 140 are not divisible by any of 2, 5 or 7. As in the previous question, we start by counting the complement of the set we are interested in (because it is easier to count).

  1. Negate the statement "\(n\) is not divisible by any of 2, 5 and 7." Solution.

    \(n\) is divisible by at least one of 2, 5 or 7

  2. The set of numbers that you described in part (a) can be found using inclusion-exclusion. Do so. Solution.

    Let \(A_2\text{,}\) \(A_5\) and \(A_7\) be the set of numbers divisible by 2, 5, and 7, respectively. We have

    \begin{equation*} \begin{array}{ccc} |A_2| = 70 & |A_5| = 28 & |A_7| = 20 \\ |A_2 \cap A_5| = 14 & |A_2 \cap A_7| = 10 & |A_5 \cap A_7| = 4 \\ &|A_2 \cap A_5 \cap A_7| = 2 \\ \end{array} \end{equation*}

    By inclusion-exclusion the answer is

    \begin{equation*} 70+28+20 - 14 - 10 - 4 + 2 = 92 \end{equation*}

  3. Use your answer to (b) to find how many numbers in [140] are not divisible by any of 2, 5 and 7. Solution.

    We use the useful theorem "good = all - bad" to find that

    \begin{equation*} 140 -92 = 48 \end{equation*}

3. Sharing French Fries.

Anna, Boris, Clyde and Denise are sharing a basket of 50 french fries. How many ways are there for them to share the fries, assuming nobody gets more than 15 fries?

  1. How many ways are there, with no restrictions, to distribute 50 identical french fries among 4 distinct friends? Solution.

    We have 50 identical fries (balls) to give to 4 distinct friends (boxes). Repetition is allowed and boxes can be empty. The number of ways is \({50+4-1 \choose 50} = {53 \choose 50}\text{.}\)

  2. Let \(A\) be the set of outcomes in which Anna gets 16 or more fries. What is \(|A|\text{?}\) (Hint: first give away 16 fries to Anna, then distribute the rest freely among the 4 friends.) Define similar sets \(B,C,D\) for Boris, Clyde and Denise. Find \(|A|+|B|+|C|+|D|\text{.}\) Solution.

    After reserving 16 fries for Anna, we have 34 fries left over, to distribute any way we like. The number of ways is \({34+4-1 \choose 50} = {37 \choose 34}\text{.}\) The same argument holds for Boris, Clyde and Denise. so
    \begin{equation*} |A|+|B|+|C|+|D| = 4 {37 \choose 34}. \end{equation*}

  3. What is \(|A \cap B|\text{?}\) (Hint: first give away 16 fries to Anna and 16 more to Boris, then distribute the rest freely.) What is \(| A \cap B| + | A \cap C| + | A \cap D| + | B \cap C| + | B \cap D| + | C \cap D|\text{?}\) Solution.

    After reserving 16 fries for Anna, and 16 fries for Boris, we have 18 fries left over, to distribute any way we like. The number of ways is \({18+4-1 \choose 18} = {21 \choose 18}\text{.}\) The same argument holds for any pair of friends, so
    \begin{equation*} | A \cap B| + | A \cap C| + | A \cap D| + | B \cap C| + | B \cap D| + | C \cap D|= 6 {21 \choose 18}. \end{equation*}

  4. Use similar reasoning to part (c) to find the sum of the sizes of all intersections involving 3 of the sets \(A,B,C,D\text{.}\) Solution.

    After reserving 16 fries for Anna, and 16 fries for Boris, and 16 fries for Clyde, we have 2 fries left over, to distribute any way we like. The number of ways is \({2+4-1 \choose 18} = {5 \choose 2}\text{.}\) The same argument holds for any triple of friends, so
    \begin{equation*} | A \cap B \cap C| + | A \cap B \cap D| + | A \cap C \cap D| + | B \cap C \cap D| = 4 {5 \choose 3}. \end{equation*}

  5. Find \(|A \cap B \cap C \cap D|\text{.}\) Solution.

    There are not enough fries to give 16 fries to each of 4 people. So \(|A \cap B \cap C \cap D|=0\)

  6. Use inclusion-exclusion to find the total number of ways for the friends to share 50 fries where no one gets more than 15 fries. Solution.

    Our final answer is
    \begin{equation*} {53 \choose 50} - 4 {37 \choose 34} + 6 {21 \choose 18} - 4 {5 \choose 3} + 0. \end{equation*}