The Inclusion-Exclusion Principle – Notes, Examples & Practice Questions (Discrete Mathematics)

Discrete Mathematics and Combinatorics

Introduction: When Simple Addition Fails

My dear student, let me start with a simple question. Suppose 30 students in a class take Mathematics and 25 students take Biology. Can we say there are 30 + 25 = 55 students in total?

The answer is: Not necessarily! What if some students take both subjects? For example, if 10 students take both Mathematics and Biology, then those 10 students were counted twice — once in the 30 and once in the 25. So the actual total would be 30 + 25 − 10 = 45.

This is exactly the problem the Inclusion-Exclusion Principle solves. It corrects our count when sets overlap. You already saw a hint of this when we studied the Addition Principle — remember, the Addition Principle only works when events are mutually exclusive (no overlap). But in real life, sets often overlap, and that is when Inclusion-Exclusion becomes essential.

The Core Idea: When we add the sizes of two sets, the elements in the intersection are counted twice. So we must subtract the intersection once to correct the count. This is “inclusion” (adding both sets) followed by “exclusion” (removing the double-counted part).

Part 1: Inclusion-Exclusion for Two Sets

The Formula

Inclusion-Exclusion Principle for Two Sets:

\[n(A \cup B) = n(A) + n(B) – n(A \cap B)\]

In words: The number of elements in A or B (or both) equals the number in A plus the number in B, minus the number in both A and B.

Understanding with a Venn Diagram

Let me show you what happens visually. Think of two overlapping circles:

          U (Universal Set)
     _______________
    |       _______  |
    |      /   A   \ |
    |     /    ___  \|
    |    |   / B  \  |
    |    |  |  X  |  |
    |    |   \____/  |
    |     \        / |
    |      \______/  |
    |________________|
X = the intersection A ∩ B (counted twice if we just add n(A) + n(B))

When we add n(A) + n(B), the region X (the intersection) is counted two times. So we subtract n(A ∩ B) once to count it only one time. That is the whole principle!

Example 1: Students Taking Two Courses

Problem: In a survey of 140 sophomore students at a college:

  • 60 completed requirement A
  • 45 completed requirement B
  • 20 completed both A and B

Find: (a) the number who completed at least one requirement, (b) the number who completed exactly one requirement, (c) the number who completed neither requirement.

Solution:

(a) At least one requirement: This means A or B or both, which is \(A \cup B\).

\[n(A \cup B) = n(A) + n(B) – n(A \cap B) = 60 + 45 – 20 = 85\]

So 85 students completed at least one requirement.

(b) Exactly one requirement: This means A only or B only (but NOT both).

  • A only (A but not B): \(n(A) – n(A \cap B) = 60 – 20 = 40\)
  • B only (B but not A): \(n(B) – n(A \cap B) = 45 – 20 = 25\)

Total exactly one = 40 + 25 = 65 students.

(c) Neither requirement: These are students not in \(A \cup B\).

\[n(A \cup B)^c = n(U) – n(A \cup B) = 140 – 85 = 55\]

So 55 students completed neither requirement.

Key Points — Two Sets:
  • At least one = \(n(A \cup B) = n(A) + n(B) – n(A \cap B)\)
  • Exactly one = \([n(A) – n(A \cap B)] + [n(B) – n(A \cap B)]\)
  • Neither = \(n(U) – n(A \cup B)\)
  • Only A (not B) = \(n(A) – n(A \cap B)\)

Question: A list A contains 30 students in a Mathematics class, and a list B contains 35 students in an English class. There are 20 names on both lists. Find: (a) the number only on list A, (b) the number only on list B, (c) the number on exactly one list.

(a) Only on list A: \(n(A) – n(A \cap B) = 30 – 20 = 10\)

(b) Only on list B: \(n(B) – n(A \cap B) = 35 – 20 = 15\)

(c) Exactly one list: This is the symmetric difference \(A \oplus B = (A – B) \cup (B – A) = 10 + 15 = 25\)

You could also find this as: \(n(A \cup B) – n(A \cap B) = (30 + 35 – 20) – 20 = 45 – 20 = 25\) ✓

Example 2: Magazine Readers

Problem: In a survey of 120 people:

  • 65 read Newsweek
  • 45 read Time
  • 42 read Fortune
  • 20 read both Newsweek and Time
  • 25 read both Newsweek and Fortune
  • 15 read both Time and Fortune
  • 8 read all three magazines

Find: (a) the number who read at least one magazine, (b) fill in all eight regions of the Venn diagram, (c) the number who read exactly one magazine.

Solution:

(a) At least one magazine: We need \(n(N \cup T \cup F)\). But wait — this involves three sets, not two! We will learn the three-set formula next. But let me give you a preview using the Venn diagram method.

(b) Filling the Venn diagram regions: Always start from the innermost region and work outward!

           N = Newsweek, T = Time, F = Fortune

               _________
              /    N     \
             / ____+____  \
            / /  NT  | NF \ \
           | |  12  | 17  | |
           | |_______|_____| |
           | |   8   |   F | |
           | | (NTF) | 10  | |
            \ \_______|___/ /
             \   18   | TF /
              \_______+__/
                NTF only=8
  • All three (NTF): 8 (given directly)
  • Newsweek and Time only (NT, not F): \(20 – 8 = 12\)
  • Newsweek and Fortune only (NF, not T): \(25 – 8 = 17\)
  • Time and Fortune only (TF, not N): \(15 – 8 = 7\)
  • Newsweek only: \(65 – 12 – 8 – 17 = 28\)
  • Time only: \(45 – 12 – 8 – 7 = 18\)
  • Fortune only: \(42 – 17 – 8 – 7 = 10\)
  • No magazine: \(120 – (28 + 12 + 18 + 17 + 8 + 7 + 10) = 120 – 100 = 20\)

Check: \(28 + 12 + 18 + 17 + 8 + 7 + 10 + 20 = 120\) ✓

(c) Exactly one magazine: \(28 + 18 + 10 = \mathbf{56}\)

Important Rule: When filling Venn diagram regions, always start from the innermost intersection (the region where all sets overlap) and work your way outward. If you start from the outside, you will make mistakes because the outer numbers include the inner overlaps.

Question: In a class of 50 students, 30 play football, 25 play basketball, and 15 play both. How many play neither sport? How many play exactly one sport?

Neither sport: \(n(F \cup B) = 30 + 25 – 15 = 40\). Neither = \(50 – 40 = 10\).

Exactly one sport: Football only = \(30 – 15 = 15\). Basketball only = \(25 – 15 = 10\). Total = \(15 + 10 = 25\).

Question: Suppose |A| = 10 and |B| = 15. What is the largest possible value of |A ∩ B|? What is the smallest possible value?

Largest |A ∩ B| = 10. The intersection cannot exceed the smaller set. If A is entirely inside B, then A ∩ B = A, giving |A ∩ B| = 10.

Smallest |A ∩ B| = 0. The sets could be completely disjoint (no common elements).

Part 2: Inclusion-Exclusion for Three Sets

The Formula

Now let us extend the principle to three sets. This is where many exam questions come from, so pay close attention!

Inclusion-Exclusion Principle for Three Sets:

\[n(A \cup B \cup C) = n(A) + n(B) + n(C) – n(A \cap B) – n(A \cap C) – n(B \cap C) + n(A \cap B \cap C)\]

Let me explain the pattern carefully:

  • First step (+): Add all individual sets → \(n(A) + n(B) + n(C)\)
  • Second step (−): Subtract all pairwise intersections → \(- n(A \cap B) – n(A \cap C) – n(B \cap C)\)
  • Third step (+): Add back the triple intersection → \(+ n(A \cap B \cap C)\)
Why do we add back the triple intersection? Think about it step by step. In the first step, elements in all three sets are counted three times (once in each of n(A), n(B), n(C)). In the second step, elements in all three sets appear in each of the three pairwise intersections, so they are subtracted three times. So after two steps: \(3 – 3 = 0\) — the triple-intersection elements have been completely removed! We need to add them back once so they are counted exactly once. That is why the third step is +.

Example 3: Students Studying Languages

Problem: Find the number of Mathematics students at a college taking at least one of French, German, and Russian, given:

  • 65 study French (F)
  • 45 study German (G)
  • 42 study Russian (R)
  • 20 study French and German
  • 25 study French and Russian
  • 15 study German and Russian
  • 8 study all three languages

Solution: Apply the three-set formula directly:

\[\begin{aligned} n(F \cup G \cup R) &= n(F) + n(G) + n(R) \\ &\quad – n(F \cap G) – n(F \cap R) – n(G \cap R) \\ &\quad + n(F \cap G \cap R) \\ &= 65 + 45 + 42 – 20 – 25 – 15 + 8 \\ &= 152 – 60 + 8 = 100 \end{aligned}\]

So 100 students study at least one of the three languages.

Example 4: Finding Each Region

Problem: Using the same data as Example 3, find the number of students who study: (a) exactly one language, (b) exactly two languages, (c) only French.

Solution: First, fill in all eight regions of the Venn diagram (starting from the center):

  • All three (F ∩ G ∩ R): 8
  • French and German only: \(20 – 8 = 12\)
  • French and Russian only: \(25 – 8 = 17\)
  • German and Russian only: \(15 – 8 = 7\)
  • French only: \(65 – 12 – 8 – 17 = 28\)
  • German only: \(45 – 12 – 8 – 7 = 18\)
  • Russian only: \(42 – 17 – 8 – 7 = 10\)
See also  The Binomial Theorem – Complete Lesson

(a) Exactly one language: \(28 + 18 + 10 = \mathbf{56}\)

(b) Exactly two languages: \(12 + 17 + 7 = \mathbf{36}\)

(c) Only French: \(\mathbf{28}\)

Check: \(56 + 36 + 8 = 100\) ✓ (matches our answer from Example 3)

Key Points — Three Sets:
  • Always fill Venn diagram regions from the center outward
  • Pairwise intersection “only” = pairwise − triple
  • Single set “only” = single set − (its two pairwise intersections) − triple
  • Exactly one = sum of three “only” regions
  • Exactly two = sum of three “pairwise only” regions
  • At least one = exactly one + exactly two + exactly three

Question: In a group of 200 students: 120 take Physics, 90 take Chemistry, 70 take Biology. 50 take Physics and Chemistry, 40 take Physics and Biology, 30 take Chemistry and Biology, and 10 take all three. Find: (a) how many take at least one science, (b) how many take exactly two sciences, (c) how many take none of these sciences.

(a) \(n(P \cup C \cup B) = 120 + 90 + 70 – 50 – 40 – 30 + 10 = 280 – 120 + 10 = 170\)

(b) PC only = 50 − 10 = 40. PB only = 40 − 10 = 30. CB only = 30 − 10 = 20. Exactly two = 40 + 30 + 20 = 90.

(c) None = 200 − 170 = 30.

Question: If |A| = 8 and |B| = 5, what is |A ∪ B| + |A ∩ B|?

We know \(|A \cup B| = |A| + |B| – |A \cap B|\).

So \(|A \cup B| + |A \cap B| = |A| + |B| – |A \cap B| + |A \cap B| = |A| + |B| = 8 + 5 = \mathbf{13}\).

Interesting! The sum of the union and intersection always equals the sum of the individual sizes, regardless of how much they overlap!

Part 3: The General Inclusion-Exclusion Principle

Formula for n Sets

What if we have 4, 5, or even more sets? The pattern continues. Let me state the general formula:

General Inclusion-Exclusion Principle:

\[n(A_1 \cup A_2 \cup \cdots \cup A_m) = \sum_{i} n(A_i) – \sum_{i < j} n(A_i \cap A_j) + \sum_{i < j < k} n(A_i \cap A_j \cap A_k) - \cdots + (-1)^{m+1} n(A_1 \cap A_2 \cap \cdots \cap A_m)\]

In simpler words:

  • Add all single sets
  • Subtract all pairwise intersections
  • Add all triple intersections
  • Subtract all 4-way intersections
  • Continue alternating signs…
  • The last term has sign \((-1)^{m+1}\)

Example 5: Four Sets

Problem: A survey of 500 households found:

  • 210 have a radio (R)
  • 180 have a TV (T)
  • 120 have a newspaper (N)
  • 85 have internet (I)
  • 80 have radio and TV
  • 50 have radio and newspaper
  • 45 have radio and internet
  • 55 have TV and newspaper
  • 40 have TV and internet
  • 30 have newspaper and internet
  • 15 have radio, TV, and newspaper
  • 10 have radio, TV, and internet
  • 8 have radio, newspaper, and internet
  • 5 have TV, newspaper, and internet
  • 2 have all four

Find how many households have at least one of these four media.

Solution: Using the 4-set formula:

\[\begin{aligned} n(R \cup T \cup N \cup I) &= (210 + 180 + 120 + 85) \\ &\quad – (80 + 50 + 45 + 55 + 40 + 30) \\ &\quad + (15 + 10 + 8 + 5) \\ &\quad – 2 \\ &= 595 – 300 + 38 – 2 \\ &= \mathbf{331} \end{aligned}\]

So 331 households have at least one media source, and \(500 – 331 = 169\) have none.

Exam Tip: For 4-set problems, you need to be very careful to include ALL pairwise intersections (there are \(\binom{4}{2} = 6\) of them) and ALL triple intersections (there are \(\binom{4}{3} = 4\) of them). Missing even one will give a wrong answer!

Part 4: Using Complements with Inclusion-Exclusion

Sometimes it is easier to find how many elements are in none of the sets, rather than how many are in at least one. The complement approach is very powerful.

Complement Formula:

\[n(A_1^c \cap A_2^c \cap \cdots \cap A_m^c) = n(U) – n(A_1 \cup A_2 \cup \cdots \cup A_m)\]

In words: The number of elements in NONE of the sets equals the universe size minus the number in at least one set.

Example 6: Numbers Divisible by Primes

Problem: How many integers from 1 to 100 are NOT divisible by 2, 3, or 5?

Solution: Let A = multiples of 2, B = multiples of 3, C = multiples of 5. We want \(n(A^c \cap B^c \cap C^c)\).

First, find \(n(A \cup B \cup C)\):

  • \(n(A) = \lfloor 100/2 \rfloor = 50\) (multiples of 2)
  • \(n(B) = \lfloor 100/3 \rfloor = 33\) (multiples of 3)
  • \(n(C) = \lfloor 100/5 \rfloor = 20\) (multiples of 5)
  • \(n(A \cap B) = \lfloor 100/6 \rfloor = 16\) (multiples of lcm(2,3) = 6)
  • \(n(A \cap C) = \lfloor 100/10 \rfloor = 10\) (multiples of lcm(2,5) = 10)
  • \(n(B \cap C) = \lfloor 100/15 \rfloor = 6\) (multiples of lcm(3,5) = 15)
  • \(n(A \cap B \cap C) = \lfloor 100/30 \rfloor = 3\) (multiples of lcm(2,3,5) = 30)
\[n(A \cup B \cup C) = 50 + 33 + 20 – 16 – 10 – 6 + 3 = 74\]
\[n(A^c \cap B^c \cap C^c) = 100 – 74 = \mathbf{26}\]

So 26 integers from 1 to 100 are not divisible by 2, 3, or 5.

Question: How many integers from 1 to 200 are NOT divisible by 3 or 7?

Let A = multiples of 3, B = multiples of 7.

  • \(n(A) = \lfloor 200/3 \rfloor = 66\)
  • \(n(B) = \lfloor 200/7 \rfloor = 28\)
  • \(n(A \cap B) = \lfloor 200/21 \rfloor = 9\) (multiples of 21)

\(n(A \cup B) = 66 + 28 – 9 = 85\)

Not divisible by 3 or 7 = \(200 – 85 = \mathbf{115}\)

Part 5: Special Counting Formulas from Inclusion-Exclusion

Exactly One, Exactly Two, Exactly Three

Many exam questions ask: “How many elements are in exactly one set?” or “exactly two sets?” Here are the formulas:

For Three Sets A, B, C:

Exactly one set:
\[n(\text{exactly one}) = n(A) + n(B) + n(C) – 2[n(A \cap B) + n(A \cap C) + n(B \cap C)] + 3 \cdot n(A \cap B \cap C)\]

Exactly two sets:
\[n(\text{exactly two}) = n(A \cap B) + n(A \cap C) + n(B \cap C) – 3 \cdot n(A \cap B \cap C)\]

Exactly three sets:
\[n(\text{exactly three}) = n(A \cap B \cap C)\]

But honestly, instead of memorizing these formulas, I recommend using the Venn diagram method (fill from center outward). It is safer and less prone to errors. Let me show you with an example.

Example 7: Exactly Two Sets Using Venn Diagram

Problem: Among 100 students: 40 study Math, 35 study Physics, 30 study Chemistry. 15 study Math and Physics, 10 study Math and Chemistry, 12 study Physics and Chemistry, and 5 study all three. How many study exactly two subjects?

Solution using Venn diagram (center outward):

  • All three: 5
  • Math and Physics only: \(15 – 5 = 10\)
  • Math and Chemistry only: \(10 – 5 = 5\)
  • Physics and Chemistry only: \(12 – 5 = 7\)

Exactly two = \(10 + 5 + 7 = \mathbf{22}\)

Using the formula: \(15 + 10 + 12 – 3(5) = 37 – 15 = 22\) ✓ Same answer!

Question: Using the data from Example 7, find how many study exactly one subject.

Continue filling the Venn diagram:

  • Math only: \(40 – 10 – 5 – 5 = 20\)
  • Physics only: \(35 – 10 – 5 – 7 = 13\)
  • Chemistry only: \(30 – 5 – 5 – 7 = 13\)

Exactly one = \(20 + 13 + 13 = \mathbf{46}\)

Check: Exactly one (46) + Exactly two (22) + Exactly three (5) = 73. And \(n(M \cup P \cup C) = 40 + 35 + 30 – 15 – 10 – 12 + 5 = 73\) ✓

Students studying none = \(100 – 73 = 27\).

Part 6: Inclusion-Exclusion for Properties of Integers

Inclusion-Exclusion is very useful for counting integers that have certain divisibility properties. Let me give you another example.

Example 8: Counting Using Divisibility

Problem: How many positive integers less than 1000 are divisible by 5 or 7?

Solution: Let A = integers from 1 to 999 divisible by 5, B = integers from 1 to 999 divisible by 7.

  • \(n(A) = \lfloor 999/5 \rfloor = 199\)
  • \(n(B) = \lfloor 999/7 \rfloor = 142\)
  • \(n(A \cap B) = \lfloor 999/35 \rfloor = 28\) (divisible by lcm(5,7) = 35)
\[n(A \cup B) = 199 + 142 – 28 = 313\]

So 313 positive integers less than 1000 are divisible by 5 or 7.

Question: How many positive integers from 1 to 500 are divisible by at least one of 2, 3, or 5?

Let A = div by 2, B = div by 3, C = div by 5.

  • \(n(A) = \lfloor 500/2 \rfloor = 250\)
  • \(n(B) = \lfloor 500/3 \rfloor = 166\)
  • \(n(C) = \lfloor 500/5 \rfloor = 100\)
  • \(n(A \cap B) = \lfloor 500/6 \rfloor = 83\)
  • \(n(A \cap C) = \lfloor 500/10 \rfloor = 50\)
  • \(n(B \cap C) = \lfloor 500/15 \rfloor = 33\)
  • \(n(A \cap B \cap C) = \lfloor 500/30 \rfloor = 16\)
\[n(A \cup B \cup C) = 250 + 166 + 100 – 83 – 50 – 33 + 16 = 366\]

Answer: 366 integers.

Key Points — General Inclusion-Exclusion:
  • The signs alternate: +, −, +, −, …
  • For m sets, there are \(\binom{m}{k}\) terms at the k-th level
  • The last term (m-way intersection) has sign \((-1)^{m+1}\)
  • For divisibility problems, use lcm for intersections
  • The Venn diagram method is often safer than memorizing formulas for “exactly k” problems
  • Always check your answer: the sum of all regions should equal n(U)

Question: In a survey of 100 people: 60 like tea, 50 like coffee, 35 like milk. 25 like tea and coffee, 20 like tea and milk, 15 like coffee and milk, and 10 like all three. How many like exactly one beverage?

Fill Venn diagram from center:

  • All three: 10
  • Tea and coffee only: 25 − 10 = 15
  • Tea and milk only: 20 − 10 = 10
  • Coffee and milk only: 15 − 10 = 5
  • Tea only: 60 − 15 − 10 − 10 = 25
  • Coffee only: 50 − 15 − 10 − 5 = 20
  • Milk only: 35 − 10 − 5 − 10 = 10

Exactly one = 25 + 20 + 10 = 55

Check: Total in at least one = 25 + 15 + 20 + 10 + 10 + 5 + 10 = 95. None = 100 − 95 = 5. Sum = 95 + 5 = 100 ✓

Revision Summary: Inclusion-Exclusion Principle

1. Two-Set Formula

\[n(A \cup B) = n(A) + n(B) – n(A \cap B)\]

2. Three-Set Formula

\[n(A \cup B \cup C) = n(A) + n(B) + n(C) – n(A \cap B) – n(A \cap C) – n(B \cap C) + n(A \cap B \cap C)\]

3. General Formula (m Sets)

\[n\Big(\bigcup_{i=1}^{m} A_i\Big) = \sum n(A_i) – \sum n(A_i \cap A_j) + \sum n(A_i \cap A_j \cap A_k) – \cdots\]

Signs alternate: +, −, +, −, …

4. Complement Approach

\[n(\text{none}) = n(U) – n(A_1 \cup A_2 \cup \cdots \cup A_m)\]

5. Useful Derived Formulas

QuantityHow to Find
Only A\(n(A) – n(A \cap B)\)
Exactly one (2 sets)\(n(A) + n(B) – 2n(A \cap B)\)
Exactly two (3 sets)Sum of pairwise − 3 × triple
Neither\(n(U) – n(A \cup B)\)
\(|A \cup B| + |A \cap B|\)Always equals \(|A| + |B|\)

6. Venn Diagram Filling Rule

ALWAYS start from the innermost region (triple intersection) and work outward.

Step 1: Fill the center (all sets overlap)
Step 2: Fill pairwise-only regions (pairwise minus center)
Step 3: Fill single-only regions (single minus all overlapping parts)
Step 4: Fill “none” region (universe minus all filled regions)
Step 5: Verify: sum of all regions = n(U)

7. For Divisibility Problems

  • Multiples of a in range 1 to N: \(\lfloor N/a \rfloor\)
  • Multiples of both a and b: \(\lfloor N/\text{lcm}(a,b) \rfloor\)
  • Multiples of a, b, and c: \(\lfloor N/\text{lcm}(a,b,c) \rfloor\)

8. Common Exam Mistakes

  • Forgetting to subtract the intersection in the 2-set case
  • Missing a pairwise intersection in the 3-set or 4-set case
  • Getting the sign wrong (adding when should subtract, or vice versa)
  • Starting Venn diagram from outside instead of center
  • Forgetting that pairwise intersections INCLUDE the triple intersection
  • Confusing “at least one” with “exactly one”

Mini Exam

Q1: In a class of 45 students, 22 play cricket, 18 play volleyball, and 5 play both. How many play neither?

\(n(C \cup V) = 22 + 18 – 5 = 35\). Neither = \(45 – 35 = 10\).

Q2: State the Inclusion-Exclusion formula for three sets and explain why the triple intersection is added (not subtracted).

\[n(A \cup B \cup C) = n(A) + n(B) + n(C) – n(A \cap B) – n(A \cap C) – n(B \cap C) + n(A \cap B \cap C)\]

The triple intersection is added because: elements in \(A \cap B \cap C\) are counted 3 times in the first sum, then subtracted 3 times in the second sum (since they appear in all three pairwise intersections). So after two steps they have been counted \(3 – 3 = 0\) times — they have been completely removed! We add them back once so they are counted exactly one time.

Q3: How many integers from 1 to 300 are not divisible by 2, 3, or 5?

  • \(n(A) = \lfloor 300/2 \rfloor = 150\)
  • \(n(B) = \lfloor 300/3 \rfloor = 100\)
  • \(n(C) = \lfloor 300/5 \rfloor = 60\)
  • \(n(A \cap B) = \lfloor 300/6 \rfloor = 50\)
  • \(n(A \cap C) = \lfloor 300/10 \rfloor = 30\)
  • \(n(B \cap C) = \lfloor 300/15 \rfloor = 20\)
  • \(n(A \cap B \cap C) = \lfloor 300/30 \rfloor = 10\)
\[n(A \cup B \cup C) = 150 + 100 + 60 – 50 – 30 – 20 + 10 = 220\]

Not divisible by 2, 3, or 5 = \(300 – 220 = 80\).

Challenge Exam Questions — Mixed Types

These questions are at the level of midterm and final exams. Try each one before looking at the answer!

Multiple Choice Questions (MCQs)

MCQ 1: If n(A) = 15, n(B) = 12, and n(A ∪ B) = 22, then n(A ∩ B) equals:
(a) 3   (b) 5   (c) 7   (d) 27

Answer: (b) 5

Using \(n(A \cup B) = n(A) + n(B) – n(A \cap B)\):

\(22 = 15 + 12 – n(A \cap B)\), so \(n(A \cap B) = 27 – 22 = 5\).

MCQ 2: In a group of 70 people, 40 speak Amharic, 35 speak Oromo, and 15 speak both. How many speak neither language?
(a) 5   (b) 10   (c) 15   (d) 20

Answer: (b) 10

\(n(A \cup O) = 40 + 35 – 15 = 60\). Neither = \(70 – 60 = 10\).

MCQ 3: For three sets A, B, C: n(A) = 20, n(B) = 18, n(C) = 16, n(A ∩ B) = 7, n(A ∩ C) = 5, n(B ∩ C) = 4, n(A ∩ B ∩ C) = 2. Then n(A ∪ B ∪ C) equals:
(a) 40   (b) 42   (c) 38   (d) 36

Answer: (a) 40

\[n(A \cup B \cup C) = 20 + 18 + 16 – 7 – 5 – 4 + 2 = 54 – 16 + 2 = 40\]

MCQ 4: The number of integers from 1 to 100 that are divisible by 3 or 5 is:
(a) 47   (b) 53   (c) 50   (d) 33

Answer: (a) 47

\(n(A) = \lfloor 100/3 \rfloor = 33\), \(n(B) = \lfloor 100/5 \rfloor = 20\), \(n(A \cap B) = \lfloor 100/15 \rfloor = 6\).

\(n(A \cup B) = 33 + 20 – 6 = 47\).

MCQ 5: If |A ∪ B| = 25 and |A ∩ B| = 5, then |A| + |B| equals:
(a) 20   (b) 30   (c) 25   (d) 15

Answer: (b) 30

From the identity: \(|A \cup B| + |A \cap B| = |A| + |B|\). So \(|A| + |B| = 25 + 5 = 30\).

MCQ 6: In a Venn diagram of three sets, the total number of distinct regions is:
(a) 6   (b) 7   (c) 8   (d) 9

Answer: (c) 8

For three sets: 3 “only” regions + 3 “pairwise-only” regions + 1 “triple” region + 1 “none” region = 8 regions total.

MCQ 7: In a survey: 50 like mango, 40 like banana, 30 like apple. 20 like mango and banana, 15 like mango and apple, 10 like banana and apple, and 5 like all three. How many like exactly two fruits?
(a) 25   (b) 30   (c) 35   (d) 20

Answer: (b) 30

Mango-banana only: 20 − 5 = 15. Mango-apple only: 15 − 5 = 10. Banana-apple only: 10 − 5 = 5.

Exactly two = 15 + 10 + 5 = 30.

Short Answer and Proof Questions

Q8: In a class of 80 students: 45 study Mathematics, 38 study English, 30 study Biology. 18 study Mathematics and English, 15 study Mathematics and Biology, 12 study English and Biology, and 8 study all three. Find: (a) how many study none of these subjects, (b) how many study exactly one subject, (c) how many study Mathematics only.

First fill Venn diagram from center:

  • All three: 8
  • Math-English only: 18 − 8 = 10
  • Math-Biology only: 15 − 8 = 7
  • English-Biology only: 12 − 8 = 4
  • Math only: 45 − 10 − 7 − 8 = 20
  • English only: 38 − 10 − 4 − 8 = 16
  • Biology only: 30 − 7 − 4 − 8 = 11

At least one = 20 + 10 + 16 + 7 + 8 + 4 + 11 = 76

(a) None = 80 − 76 = 4

(b) Exactly one = 20 + 16 + 11 = 47

(c) Mathematics only = 20

Q9: How many integers from 1 to 1000 are NOT divisible by 4, 6, or 9?

Let A = div by 4, B = div by 6, C = div by 9.

  • \(n(A) = \lfloor 1000/4 \rfloor = 250\)
  • \(n(B) = \lfloor 1000/6 \rfloor = 166\)
  • \(n(C) = \lfloor 1000/9 \rfloor = 111\)
  • \(n(A \cap B) = \lfloor 1000/12 \rfloor = 83\) (lcm(4,6) = 12)
  • \(n(A \cap C) = \lfloor 1000/36 \rfloor = 27\) (lcm(4,9) = 36)
  • \(n(B \cap C) = \lfloor 1000/18 \rfloor = 55\) (lcm(6,9) = 18)
  • \(n(A \cap B \cap C) = \lfloor 1000/36 \rfloor = 27\) (lcm(4,6,9) = 36)
\[n(A \cup B \cup C) = 250 + 166 + 111 – 83 – 27 – 55 + 27 = 389\]

Not divisible = \(1000 – 389 = 611\)

Q10: A survey of 150 TV viewers found: 80 watch drama, 65 watch comedy, 50 watch sports. 30 watch drama and comedy, 25 watch drama and sports, 20 watch comedy and sports, and 10 watch all three. How many watch: (a) only drama and comedy (not sports), (b) at least two types, (c) exactly one type?

Venn diagram from center:

  • All three: 10
  • Drama-comedy only: 30 − 10 = 20
  • Drama-sports only: 25 − 10 = 15
  • Comedy-sports only: 20 − 10 = 10
  • Drama only: 80 − 20 − 15 − 10 = 35
  • Comedy only: 65 − 20 − 10 − 10 = 25
  • Sports only: 50 − 15 − 10 − 10 = 15

(a) Only drama and comedy = 20

(b) At least two types = 20 + 15 + 10 + 10 = 55

(c) Exactly one type = 35 + 25 + 15 = 75

Check: 75 + 55 = 130. None = 150 − 130 = 20. Sum = 130 + 20 = 150 ✓

Q11: Prove that for any two finite sets A and B: \(n(A \cup B) + n(A \cap B) = n(A) + n(B)\).

Proof:

We know that \(A = (A – B) \cup (A \cap B)\), where \(A – B\) and \(A \cap B\) are disjoint.

So \(n(A) = n(A – B) + n(A \cap B)\), giving \(n(A – B) = n(A) – n(A \cap B)\). … (i)

Similarly, \(n(B – A) = n(B) – n(A \cap B)\). … (ii)

Now \(A \cup B = (A – B) \cup (A \cap B) \cup (B – A)\), and these three sets are pairwise disjoint.

So \(n(A \cup B) = n(A – B) + n(A \cap B) + n(B – A)\)

Substituting from (i) and (ii):

\[n(A \cup B) = [n(A) – n(A \cap B)] + n(A \cap B) + [n(B) – n(A \cap B)] = n(A) + n(B) – n(A \cap B)\]

This is the Inclusion-Exclusion formula! Now adding \(n(A \cap B)\) to both sides:

\[n(A \cup B) + n(A \cap B) = n(A) + n(B) \quad \blacksquare\]

Q12: In a university, 300 students were surveyed: 180 registered for Math, 150 for Physics, 120 for Chemistry, 90 for Biology. 60 registered for Math and Physics, 50 for Math and Chemistry, 40 for Math and Biology, 45 for Physics and Chemistry, 35 for Physics and Biology, 30 for Chemistry and Biology. 15 registered for all four subjects. How many registered for at least one subject?

Using the 4-set Inclusion-Exclusion formula:

\[\begin{aligned} n(M \cup P \cup C \cup B) &= (180 + 150 + 120 + 90) \\ &\quad – (60 + 50 + 40 + 45 + 35 + 30) \\ &\quad + (\text{sum of all triple intersections}) \\ &\quad – 15 \end{aligned}\]

Wait — we need the triple intersections! The problem does not give us the triple intersections directly (e.g., Math-Physics-Chemistry only). This data is insufficient to solve the problem as stated. We would need to know how many are in each triple intersection (or all four pairwise-only values plus triple values).

This is a trick question! With 4 sets, you need ALL pairwise (6 values), ALL triple (4 values), AND the 4-way intersection. If any is missing, you cannot compute the answer. Many students make the mistake of trying to solve with incomplete data.

Answer: Cannot be determined from the given information.

Q13: How many integers from 1 to 200 are divisible by 2 or 3 but NOT by 5?

Let A = div by 2, B = div by 3, C = div by 5.

We want: \(n((A \cup B) \cap C^c) = n(A \cup B) – n((A \cup B) \cap C)\)

Now \((A \cup B) \cap C = (A \cap C) \cup (B \cap C)\), so:

\[n((A \cup B) \cap C) = n(A \cap C) + n(B \cap C) – n(A \cap B \cap C)\]

Calculate all values:

  • \(n(A) = 100\), \(n(B) = 66\), \(n(C) = 40\)
  • \(n(A \cap B) = 33\), \(n(A \cap C) = 20\), \(n(B \cap C) = 13\)
  • \(n(A \cap B \cap C) = \lfloor 200/30 \rfloor = 6\)
\[n(A \cup B) = 100 + 66 – 33 = 133\]
\[n((A \cup B) \cap C) = 20 + 13 – 6 = 27\]

Answer = \(133 – 27 = 106\)

Q14: Among 200 students: 70 take Economics, 80 take Management, 60 take Accounting. 30 take Economics and Management, 25 take Economics and Accounting, 20 take Management and Accounting. If 15 take all three and 40 take none, how many take exactly two subjects?

First verify: \(n(E \cup M \cup A) = 200 – 40 = 160\).

Check with formula: \(70 + 80 + 60 – 30 – 25 – 20 + 15 = 150\). But this should be 160!

There is an inconsistency in the problem data. The formula gives 150, but the “none” count gives 160. This means the data is contradictory — such a situation cannot exist. In an exam, you should point this out.

Answer: The given data is inconsistent.

Teacher’s note: Some exam problems have intentional errors to test whether you check your work. Always verify that your Venn diagram regions sum to n(U)!

Q15: How many permutations of the digits 1, 2, 3, 4, 5 have at least one digit in its original position? (Hint: Use Inclusion-Exclusion with derangements.)

Total permutations: \(5! = 120\).

Let \(A_i\) = permutations where digit \(i\) is in its original position (a “fixed point”).

We want \(n(A_1 \cup A_2 \cup A_3 \cup A_4 \cup A_5)\).

By Inclusion-Exclusion:

  • \(\sum n(A_i) = \binom{5}{1} \cdot 4! = 5 \times 24 = 120\)
  • \(\sum n(A_i \cap A_j) = \binom{5}{2} \cdot 3! = 10 \times 6 = 60\)
  • \(\sum n(A_i \cap A_j \cap A_k) = \binom{5}{3} \cdot 2! = 10 \times 2 = 20\)
  • \(\sum n(A_i \cap A_j \cap A_k \cap A_l) = \binom{5}{4} \cdot 1! = 5 \times 1 = 5\)
  • \(n(A_1 \cap A_2 \cap A_3 \cap A_4 \cap A_5) = \binom{5}{5} \cdot 0! = 1\)
\[n(\text{at least one fixed}) = 120 – 60 + 20 – 5 + 1 = 76\]

So 76 permutations have at least one digit in its original position.

Note: The number with NO digit in its original position (derangements) = \(120 – 76 = 44\).

Q16: In a club of 60 members: 25 play football, 20 play basketball, 15 play volleyball, 10 play table tennis. 8 play football and basketball, 7 play football and volleyball, 6 play football and table tennis, 5 play basketball and volleyball, 4 play basketball and table tennis, 3 play volleyball and table tennis. 2 play all four sports. How many play at least one sport?

This problem has the same issue as Q12 — we need the triple intersections!

For 4 sets, we need all \(\binom{4}{3} = 4\) triple intersection values. The problem only gives pairwise intersections and the 4-way intersection. Without triple intersections, the formula cannot be applied.

Answer: Cannot be determined from the given information.

The pairwise intersections given (like “8 play football and basketball”) include those who also play other sports. Without knowing how many play exactly football and basketball (and no other sport), or the triple intersections, we cannot proceed.

Q17: A factory produces items using three machines A, B, and C. Of 1000 items checked: 200 were defective by machine A’s standard, 150 by machine B’s standard, 100 by machine C’s standard. 60 were defective by both A and B standards, 40 by both A and C, 30 by both B and C, and 10 were defective by all three standards. How many items were defective by at least one standard? How many were not defective by any standard?

\[n(A \cup B \cup C) = 200 + 150 + 100 – 60 – 40 – 30 + 10 = 330\]

At least one defective standard: 330 items.

Not defective by any standard: 1000 − 330 = 670 items.

Q18: Use Inclusion-Exclusion to find how many positive integers less than 60 are relatively prime to 60 (i.e., have gcd equal to 1 with 60).

60 = 2² × 3 × 5. A number is relatively prime to 60 if it is NOT divisible by 2, 3, or 5.

So we need integers from 1 to 59 not divisible by 2, 3, or 5.

  • \(n(A) = \lfloor 59/2 \rfloor = 29\)
  • \(n(B) = \lfloor 59/3 \rfloor = 19\)
  • \(n(C) = \lfloor 59/5 \rfloor = 11\)
  • \(n(A \cap B) = \lfloor 59/6 \rfloor = 9\)
  • \(n(A \cap C) = \lfloor 59/10 \rfloor = 5\)
  • \(n(B \cap C) = \lfloor 59/15 \rfloor = 3\)
  • \(n(A \cap B \cap C) = \lfloor 59/30 \rfloor = 1\)
\[n(A \cup B \cup C) = 29 + 19 + 11 – 9 – 5 – 3 + 1 = 43\]

Relatively prime to 60 = \(59 – 43 = 16\)

This is Euler’s totient function: \(\phi(60) = 60(1 – 1/2)(1 – 1/3)(1 – 1/5) = 60 \times 1/2 \times 2/3 \times 4/5 = 16\) ✓

Q19: In a class, every student takes at least one of three subjects: Math, Physics, or Chemistry. 35 take Math, 30 take Physics, 28 take Chemistry. 12 take Math and Physics, 10 take Math and Chemistry, 8 take Physics and Chemistry. How many take all three if the class has 63 students?

Since every student takes at least one subject: \(n(M \cup P \cup C) = 63\).

Let \(x = n(M \cap P \cap C)\).

\[63 = 35 + 30 + 28 – 12 – 10 – 8 + x\]
\[63 = 93 – 30 + x = 63 + x\]

So \(63 = 63 + x\), giving \(x = 0\).

No student takes all three subjects.

Q20: How many elements are in exactly two of the sets A, B, C if: n(A) = 25, n(B) = 20, n(C) = 18, n(A ∩ B) = 8, n(A ∩ C) = 6, n(B ∩ C) = 5, n(A ∩ B ∩ C) = 2?

Exactly two = (A∩B only) + (A∩C only) + (B∩C only)

  • A∩B only = \(8 – 2 = 6\)
  • A∩C only = \(6 – 2 = 4\)
  • B∩C only = \(5 – 2 = 3\)

Exactly two = \(6 + 4 + 3 = \mathbf{13}\)

Using the formula: \(n(A \cap B) + n(A \cap C) + n(B \cap C) – 3n(A \cap B \cap C) = 8 + 6 + 5 – 6 = 13\) ✓

Related Posts

Leave a Comment

Your email address will not be published. Required fields are marked *

Copyright © 2026 ethiotemari.com | Powered by Temari

Scroll to Top