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{?}\)

  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{?}\)

  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{?}\)

  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{?}\)

  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."

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

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."

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

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

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?

  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{.}\)

  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{?}\)

  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{.}\)

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

  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.