Combinatorics path · C12

Before this lesson: Basic counting principles, Combinations and binomial coefficients

Your goal: Explain the alternating correction by tracking one object’s multiplicity.

Start with the idea and one example. Take a break before the written task if you need it. The questions are original teaching exercises, not official past-paper questions.

Inclusion–Exclusion Principle: the key idea

For finite sets A,B, |A∪B|=|A|+|B|−|A∩B| because intersection elements were counted twice. For three sets, subtract the three pairwise intersections and add the triple intersection. General inclusion–exclusion alternates signs over nonempty collections of sets. Define the forbidden properties precisely, then count objects having each collection of properties. Pairwise intersections include the triple intersection unless “exactly” is specified.

A worked example

Among 1,…,30, how many integers are divisible by 2 or 3?

There are 15 multiples of 2 and 10 of 3. The 5 multiples of 6 were counted twice, so the union has 15+10−5=20 integers.

Your turn: change one thing

How many integers from 1 to 30 are divisible by neither 2 nor 3?

Try this on paper before opening the explanation.

Compare your reasoning

The complement of the union has 30−20=10 elements.

Pause and check

A trap to avoid: Wrong intersection counts or an incorrect final sign.

Practise and adjust the level

Foundation checks the language; Core applies the method; Stretch asks you to choose or justify an idea. These are levels within this lesson. A session selects six of the nine questions; unused questions allow the level to change. Advanced theory still needs written practice.

Interactive practice loads here. You can also use the complete question set below.

Write a complete argument

Explain the coefficient of an element lying in all three sets in the three-set formula.

Planning hint

List the assumptions and the exact conclusion. Identify the definition or theorem in this lesson that connects them. Explain why its conditions hold before using it.

Read the full solution after your attempt

The element is counted three times in the single-set sum, subtracted three times in the pair-intersection sum and added once in the triple intersection. Its total coefficient is 3−3+1=1, exactly as required for membership in the union.

My proof notebook

Write on paper, or keep a draft here. Compare your reasoning with the solution only after a real attempt. The checklist is your own review, not an automatic mark.

All nine practice questions

Prefer paper or have JavaScript switched off? The complete question set, hints and solutions are here. Interactive practice uses these same questions in an order chosen from your answers.

1. For two sets, why subtract the intersection?

Foundation

  1. The union is empty
  2. It was counted twice
  3. It must never be counted
  4. The sets are equal
Hint

Track an element in both sets.

Answer and reasoning

It was counted twice. It needs coefficient one, not two.

2. In three-set inclusion–exclusion, the triple intersection is what?

Foundation

  1. Added back
  2. Subtracted twice
  3. Ignored
  4. Always empty
Hint

Track its net coefficient.

Answer and reasoning

Added back. After single and pair terms its coefficient is zero, so add it once.

3. From 1 to 30, how many multiples of 6?

Core

  1. 10
  2. 5
  3. 6
  4. 4
Hint

Use ⌊30/6⌋.

Answer and reasoning

5. The multiples are 6,12,18,24,30.

4. From 1 to 30, how many multiples of 2 or 3?

Core

  1. 10
  2. 20
  3. 25
  4. 15
Hint

Subtract multiples of 6 once.

Answer and reasoning

20. 15+10−5=20.

5. If |A|=8, |B|=7 and |A∩B|=3, what is |A∪B|?

Stretch

  1. 18
  2. 5
  3. 12
  4. 15
Hint

Apply the two-set formula.

Answer and reasoning

12. 8+7−3=12.

6. Does a pairwise intersection normally include triple-intersection elements?

Stretch

  1. No
  2. Only if the sets are equal
  3. Only for disjoint sets
  4. Yes
Hint

Intersection means belonging to both, not exactly two.

Answer and reasoning

Yes. An element in all three still belongs to each pair.

7. A complement is taken relative to what?

Foundation

  1. Only an intersection
  2. No set at all
  3. A specified universe
  4. Any larger number
Hint

Objects outside the universe are not counted.

Answer and reasoning

A specified universe. The complement consists of universe elements not in the given set.

8. If a universe has 50 objects and a union has 32, its complement has how many?

Core

  1. 18
  2. 82
  3. 32
  4. 16
Hint

Subtract from the total.

Answer and reasoning

18. 50−32=18.

9. For an element in exactly two sets of a three-set problem, its final coefficient is what?

Stretch

  1. 2
  2. 3
  3. 1
  4. 0
Hint

Count two inclusions and one subtraction.

Answer and reasoning

1. It contributes 2−1=1 and no triple-intersection term.

Choose your next step

Continue to Derangements. If this felt difficult, return to a prerequisite above. Every lesson stays open.

Open my revision list →

Original teaching material · IMOolympiad.com. Send a specific correction through our contact page. Learning progress is optional and stays in this browser.