Lesson 2: Inclusion–exclusion for overlapping sets

Integers divisible by 2, 3 or 5

SkillInclusion–exclusion

Worked example

  • Complex familiar
  • Technology free

How many integers from 1 to 1000 inclusive are divisible by 2, 3 or 5? Hence find how many are divisible by none of 2, 3 and 5.

1 of 6 steps
  1. Step 1: Define the sets

    Let AA, BB and CC be the integers from 1 to 1000 that are divisible by 2, 3 and 5 respectively. We want ∣A∪B∪C∣|A \cup B \cup C|.

Try a similar one

A fresh question of the same kind, checked as you answer, with hints and a full solution.

Method

  1. Define one set for each condition.

  2. Count each set and each intersection (an intersection of "divisible by" sets is "divisible by the lowest common multiple").

  3. Add the singles, subtract the pairs, add back the triple.

  4. "None" is the total minus the union.

Watch out for

  • Rounding 10003=333.3…\frac{1000}{3} = 333.3\ldots up to 334: there are only 333 multiples of 3 up to 1000.

  • Forgetting to add back ∣A∩B∩C∣|A \cap B \cap C|, which gives 701.

  • For divisors that share a factor, such as 4 and 6, the overlap is the multiples of the lowest common multiple (12), not of the product (24).

Save your progress with a free account