📘 1.4 The Inclusion‑Exclusion Principle – count unions correctly
Hello, students! Sometimes we need to count how many elements are in the union of two or more sets. If we just add sizes, we might double‑count elements that belong to more than one set. The Inclusion‑Exclusion Principle fixes that. This is a common exam topic – and it’s also useful in probability. Let’s learn it step by step. 🇪🇹
👩🏫 Remember: For two sets, we add then subtract the intersection: \(|A \cup B| = |A| + |B| – |A \cap B|\). For three sets we add pairwise intersections and then add back the triple intersection.
🧮 Inclusion‑Exclusion for two sets
For any finite sets \(A\) and \(B\):
\[ |A \cup B| = |A| + |B| – |A \cap B| \]
╔══════════════════════════╗
│ ┌─────┐ ┌─────┐ │
│ │ A │ │ B │ │
│ │ │∩│ │ │
│ └─────┘ └─────┘ │
│ add A + B, subtract │
│ overlap A∩B once. │
╚══════════════════════════╝
📚 Example 1: In a class of 32 students who save paper or bottles (or both), 30 save paper, 14 save bottles. How many save both?
Let \(P\) = paper savers, \(B\) = bottle savers. We know \(|P|=30, |B|=14, |P\cup B|=32\).
\(|P\cap B| = |P| + |B| – |P\cup B| = 30+14-32 = 12\). So 12 students save both.
Let \(P\) = paper savers, \(B\) = bottle savers. We know \(|P|=30, |B|=14, |P\cup B|=32\).
\(|P\cap B| = |P| + |B| – |P\cup B| = 30+14-32 = 12\). So 12 students save both.
🧮 Inclusion‑Exclusion for three sets
For any finite sets \(A, B, C\):
\[
\begin{aligned}
|A \cup B \cup C| &= |A| + |B| + |C| \\
&\quad – |A\cap B| – |A\cap C| – |B\cap C| \\
&\quad + |A\cap B\cap C|
\end{aligned}
\]
Why the \(+\) at the end? Because the triple intersection was subtracted too many times (it was in all three pairwise intersections).
🌍 Example 2 (classic exam problem): A college has students studying French (F), German (G), Russian (R). Given:
\(n(F)=65,\ n(G)=45,\ n(R)=42,\ n(F\cap G)=20,\ n(F\cap R)=25,\ n(G\cap R)=15,\ n(F\cap G\cap R)=8\).
How many students take at least one language?
\[ \begin{aligned} n(F\cup G\cup R) &= 65+45+42 – 20-25-15 + 8 \\ &= 152 – 60 + 8 = 100. \end{aligned} \] So 100 students take at least one.
How many students take at least one language?
\[ \begin{aligned} n(F\cup G\cup R) &= 65+45+42 – 20-25-15 + 8 \\ &= 152 – 60 + 8 = 100. \end{aligned} \] So 100 students take at least one.
sum of singles = 65+45+42 = 152
subtract pairs = -20-25-15 = -60 → subtotal 92
add triple = +8 → final 100
✏️ Another example – with students and languages
📝 Example 3 (from module, Problem 5.66 variation): In a survey of 80 students: 20 study French, 25 Spanish, 15 German; 8 study French & Spanish, 6 Spanish & German, 5 French & German; 2 study all three. Find how many study none.
First, \(|F\cup S\cup G| = 20+25+15 – 8-6-5 + 2 = 60 -19 +2 = 43\).
So none = total 80 – 43 = 37.
First, \(|F\cup S\cup G| = 20+25+15 – 8-6-5 + 2 = 60 -19 +2 = 43\).
So none = total 80 – 43 = 37.
📝 Exercise 1.4 – selected answers from the module
| Exercise (from module) | Answer / explanation |
|---|---|
| 61. 32 art students (A), 24 biology (B), 10 in both. Find (a) \(n(A\cup B)\) (b) only A (c) only B. | (a) 32+24-10=46; (b) 32-10=22; (c) 24-10=14 |
| 62. 80 car owners: 24 foreign, 60 domestic. How many own both? | 24+60-80 = 4 both. Only foreign = 20, only domestic = 56. |
| 64. 30 students: 10 got A on first test, 9 on second, 15 none. Find (a) both A’s (b) first only (c) second only. | Let A=first, B=second. n(A∪B)=30-15=15. Then n(A∩B) = n(A)+n(B)-n(A∪B)=10+9-15=4. (b) 10-4=6 (c) 9-4=5. |
| 66. 80 students, French(F) 20, Spanish(S) 25, German(G)15. Intersections: F∩S=8, S∩G=6, F∩G=5, F∩S∩G=2. Find none, only French, etc. | Union =20+25+15-8-6-5+2=43 ⇒ none=80-43=37. Only French = 20-8-5+2=9. Only Spanish & German = S∩G – triple =6-2=4. etc. |
| 67. Sets A,B,C,D with sizes 50,60,70,80; each pair 20; each triple 10; all four 5. Find union. | s1=260, s2=6*20=120, s3=4*10=40, s4=5 ⇒ union = 260-120+40-5 = 175. |
✍️ Exam‑style questions – test yourself
1️⃣ In a class of 40 students, 22 like football, 18 like basketball, and 6 like both. How many like at least one sport?
A) 34 B) 40 C) 28 D) 46
Correct: A) 34
\(|F\cup B| = 22+18-6 = 34\).
\(|F\cup B| = 22+18-6 = 34\).
2️⃣ Out of 50 people, 30 read paper A, 20 read paper B, 15 read paper C, 10 read A∩B, 5 read A∩C, 8 read B∩C, and 3 read all three. How many read at least one?
A) 45 B) 48 C) 40 D) 52
Correct: A) 45
Union = 30+20+15 -10-5-8 +3 = 65 -23 +3 = 45.
Union = 30+20+15 -10-5-8 +3 = 65 -23 +3 = 45.
3️⃣ Using data from Q2, how many read only paper A (and not B or C)?
A) 18 B) 12 C) 15 D) 10
Correct: A) 18
Only A = \(|A| – |A\cap B| – |A\cap C| + |A\cap B\cap C|\) = 30 -10 -5 +3 = 18.
Only A = \(|A| – |A\cap B| – |A\cap C| + |A\cap B\cap C|\) = 30 -10 -5 +3 = 18.
4️⃣ 100 people were asked about brands X, Y, Z. Results: X=40, Y=35, Z=30, X∩Y=15, X∩Z=12, Y∩Z=10, X∩Y∩Z=5. How many buy none of the three?
A) 23 B) 27 C) 30 D) 35
Correct: B) 27
Union = 40+35+30 -15-12-10 +5 = 105-37+5 = 73. None = 100-73 = 27.
Union = 40+35+30 -15-12-10 +5 = 105-37+5 = 73. None = 100-73 = 27.
5️⃣ In a city, 60% speak Amharic, 40% speak Oromo, and 20% speak both. What percentage speak at least one of these languages?
A) 80% B) 100% C) 60% D) 40%
Correct: A) 80%
\(60+40-20 = 80\).
\(60+40-20 = 80\).
6️⃣ For three sets A,B,C we know \(|A|=15, |B|=12, |C|=10, |A\cup B\cup C|=25, |A\cap B|=4, |A\cap C|=3, |B\cap C|=5\). Find \(|A\cap B\cap C|\).
A) 2 B) 1 C) 0 D) 3
Correct: C) 0
Using formula: \(25 = 15+12+10 -4-3-5 + T \Rightarrow 25 = 37 -12 + T \Rightarrow 25 = 25 + T \Rightarrow T=0\).
Using formula: \(25 = 15+12+10 -4-3-5 + T \Rightarrow 25 = 37 -12 + T \Rightarrow 25 = 25 + T \Rightarrow T=0\).
📌 Exam tips for Inclusion‑Exclusion:
- Always identify the universal set and the subsets you need.
- For two sets: \(|A\cup B| = |A|+|B| – |A\cap B|\). For three sets, write the formula fully before plugging numbers.
- If they ask “only A” (and not B or C), remember: only A = \(|A| – |A\cap B| – |A\cap C| + |A\cap B\cap C|\).
- When you have totals and need intersection, rearrange the formula.
- Don’t forget to subtract triple intersection only once at the end (add it back).
🌟 Practice makes perfect – use inclusion‑exclusion in probability and counting. In the next section we cover the pigeonhole principle. Keep going! 🇪🇹