Counting with Sets

The question that drives this entire topic

In a group of 100 students:

• 60 study Mathematics
• 45 study Physics
• 30 study Chemistry
• 20 study both Mathematics and Physics
• 15 study both Physics and Chemistry
• 12 study both Mathematics and Chemistry
• 5 study all three

How many students study at least one of the three subjects?

You cannot just add 60 + 45 + 30 = 135. That exceeds 100, and clearly students are being counted multiple times.

You need the Inclusion-Exclusion Principle.

---

Two Sets — The Formula and Its Proof

For any two finite sets A and B:

$\boxed\{n(A \cup B) = n(A) + n(B) - n(A \cap B)\}$

Proof

Partition A ∪ B into three disjoint pieces:

1. A only: elements in A but not B → A − B
2. Both: elements in both → A ∩ B
3. B only: elements in B but not A → B − A

These three pieces are pairwise disjoint and their union is A ∪ B. So:

n(A ∪ B) = n(A − B) + n(A ∩ B) + n(B − A)

Also: n(A) = n(A − B) + n(A ∩ B), so n(A − B) = n(A) − n(A ∩ B). Similarly: n(B − A) = n(B) − n(A ∩ B).

Therefore: n(A ∪ B) = (n(A) − n(A ∩ B)) + n(A ∩ B) + (n(B) − n(A ∩ B)) = n(A) + n(B) − n(A ∩ B). □

Visualizing the counting

When you add n(A) + n(B), elements in A ∩ B are counted twice (once in each). Subtracting n(A ∩ B) once corrects this — every element ends up counted exactly once.

This "subtract what you double-counted" principle generalizes to any number of sets.

---

The General Pattern — Three Sets

For three sets A, B, C:

$\boxed\{n(A \cup B \cup C) = n(A) + n(B) + n(C) - n(A \cap B) - n(B \cap C) - n(A \cap C) + n(A \cap B \cap C)\}$

Why this formula?

Track how many times each element is counted by n(A) + n(B) + n(C):

• An element in exactly one set (say only A): counted 1 time. After subtracting intersections and adding triple: 1 − 0 − 0 − 0 + 0 = 1 ✓
• An element in exactly two sets (say A and B, not C): counted 2 times by the sums. Subtract n(A∩B): −1. Net = 2 − 1 = 1 ✓
• An element in all three sets: counted 3 times. Subtract n(A∩B)+n(B∩C)+n(A∩C) = −3. Add n(A∩B∩C) = +1. Net = 3 − 3 + 1 = 1 ✓

Every element ends up counted exactly once. □

Proof by two-set inclusion-exclusion

Let A ∪ B = D. Then: n(D ∪ C) = n(D) + n(C) − n(D ∩ C)

n(D) = n(A ∪ B) = n(A) + n(B) − n(A ∩ B)

n(D ∩ C) = n((A ∪ B) ∩ C) = n((A ∩ C) ∪ (B ∩ C)) [distributive law] = n(A ∩ C) + n(B ∩ C) − n(A ∩ B ∩ C)

Substituting: n(A ∪ B ∪ C) = n(A) + n(B) − n(A ∩ B) + n(C) − [n(A ∩ C) + n(B ∩ C) − n(A ∩ B ∩C)] = n(A) + n(B) + n(C) − n(A ∩ B) − n(B ∩ C) − n(A ∩ C) + n(A ∩ B ∩ C) □

---

The Region Decomposition

For three sets, the Venn diagram has exactly 8 regions. Let us label them by which sets each region belongs to:

Region	Sets	Count
Only A	A only	a
Only B	B only	b
Only C	C only	c
A and B only	A ∩ B, not C	d
B and C only	B ∩ C, not A	e
A and C only	A ∩ C, not B	f
All three	A ∩ B ∩ C	g
None	Outside all	h

Then:

• n(A) = a + d + f + g
• n(B) = b + d + e + g
• n(C) = c + e + f + g
• n(A ∩ B) = d + g
• n(B ∩ C) = e + g
• n(A ∩ C) = f + g
• n(A ∩ B ∩ C) = g
• n(A ∪ B ∪ C) = a + b + c + d + e + f + g

Strategy for JEE problems: Always fill in the Venn diagram regions from the inside out.

1. Start with g = n(A ∩ B ∩ C).
2. Then d = n(A ∩ B) − g, e = n(B ∩ C) − g, f = n(A ∩ C) − g.
3. Then a = n(A) − d − f − g, and so on.
4. h = n(U) − n(A ∪ B ∪ C).

---

The General Inclusion-Exclusion Principle (n sets)

For sets A₁, A₂, ..., Aₙ:

$n\left(\bigcup_\{i=1\}^n A_i\right) = \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)^\{n+1\} n(A_1 \cap A_2 \cap \cdots \cap A_n)$

The signs alternate: add singletons, subtract pairwise intersections, add triple intersections, subtract quadruple, etc.

Mnemonic: Odd-sized intersections are added (+), even-sized intersections are subtracted (−).

This formula has 2ⁿ − 1 terms total (one for each non-empty subset of {1, ..., n}).

---

Problems

Class 11 — Warmup

Problem 1: In a survey of 200 people: 90 read The Hindu, 80 read Times of India, 30 read both. How many read neither?

Solution: n(H ∪ T) = 90 + 80 − 30 = 140 Neither = 200 − 140 = 60

---

Problem 2: In a class, 30 students pass in English, 25 pass in Mathematics, 10 pass in both. How many pass in English but not Mathematics? How many pass in exactly one subject?

Solution: Pass in English only = 30 − 10 = 20 Pass in Mathematics only = 25 − 10 = 15 Exactly one subject = 20 + 15 = 35

---

Problem 3 (Three Sets): Answer the opening problem: 100 students, 60 M, 45 P, 30 C, 20 M∩P, 15 P∩C, 12 M∩C, 5 all three.

Solution: n(M ∪ P ∪ C) = 60 + 45 + 30 − 20 − 15 − 12 + 5 = 93

Fill in regions:

• g (all three) = 5
• d (M ∩ P only) = 20 − 5 = 15
• e (P ∩ C only) = 15 − 5 = 10
• f (M ∩ C only) = 12 − 5 = 7
• a (M only) = 60 − 15 − 7 − 5 = 33
• b (P only) = 45 − 15 − 10 − 5 = 15
• c (C only) = 30 − 10 − 7 − 5 = 8

Check: 33 + 15 + 8 + 15 + 10 + 7 + 5 = 93 ✓

Neither: 100 − 93 = 7

---

JEE Mains level

Problem 4: In a city, 60% of people read newspaper A, 40% read B, 30% read C, 20% read A and B, 15% read B and C, 10% read A and C, 5% read all three. What percentage reads at least two newspapers?

Solution: "At least two" means exactly two plus all three.

Exactly two: (A∩B only) + (B∩C only) + (A∩C only) = (20−5) + (15−5) + (10−5) = 15 + 10 + 5 = 30

All three = 5

At least two = 30 + 5 = 35%

---

Problem 5: In an examination, the ratio of students passing Mathematics to Physics to Chemistry is 3:2:1 (in terms of number). Exactly 200 pass only Mathematics, 100 pass only Physics, 50 pass only Chemistry. 40 pass Mathematics and Physics (not Chemistry), 25 pass Physics and Chemistry (not Mathematics), 30 pass Mathematics and Chemistry (not Physics). Find the number passing all three if a total of 700 students took the exam.

Solution: Let g = number passing all three.

n(M) = 200 + 40 + 30 + g n(P) = 100 + 40 + 25 + g n(C) = 50 + 25 + 30 + g

n(M ∪ P ∪ C) = 200 + 100 + 50 + 40 + 25 + 30 + g = 445 + g

Given total = 700. If all took and we use the union as all who passed: 445 + g = those who passed. But we need another condition.

Rereading — this problem needs one more constraint (typically total who pass or the ratios being used concretely). The ratio condition n(M):n(P):n(C) = 3:2:1 gives:

n(M) = 270 + g, n(P) = 165 + g, n(C) = 105 + g

Ratio: (270+g) : (165+g) : (105+g) = 3 : 2 : 1

From 3:2 ratio: 2(270+g) = 3(165+g) → 540+2g = 495+3g → g = 45

Check with 2:1 ratio: 2(105+45) = 300 = 165+45 = 210? 300 ≠ 210 × ...

Let me retry. 2(105+g) = 165+g → 210+2g = 165+g → g = −45 (impossible).

This inconsistency means the ratio condition over-constrains the system with these region values — check if this is consistent. In such JEE problems, typically only two of the three ratios are given (or just total passers). Take the problem as given: use M:C = 3:1:

(270+g)/(105+g) = 3 → 270+g = 315+3g → 2g = −45 → impossible.

Lesson: This problem has inconsistent data as stated. In JEE, always check consistency before solving. The technique is what matters: label regions, use ratio constraints, solve.

---

Problem 6 (JEE Mains 2020 pattern): In a class of 60 students, 40 like cricket, 32 like football, 24 like tennis. 20 like cricket and football, 18 like football and tennis, 12 like cricket and tennis. How many like all three? (Assuming each student likes at least one sport.)

Solution: n(A ∪ B ∪ C) = 60 (all students like at least one)

60 = 40 + 32 + 24 − 20 − 18 − 12 + g 60 = 96 − 50 + g 60 = 46 + g g = 14

Students who like all three = 14.

---

Problem 7: n(A) = 30, n(B) = 40, n(C) = 50, n(A ∩ B) = 10, n(B ∩ C) = 20, n(A ∩ C) = 5, n(A ∪ B ∪ C) = 95. Find n(A ∩ B ∩ C).

Solution: 95 = 30 + 40 + 50 − 10 − 20 − 5 + n(A ∩ B ∩ C) 95 = 120 − 35 + n(A ∩ B ∩ C) 95 = 85 + n(A ∩ B ∩ C) n(A ∩ B ∩ C) = 10

---

JEE Advanced level — Combinatorial problems using sets

Problem 8: How many integers from 1 to 300 are divisible by at least one of 3, 5, or 7?

Solution: Let A = multiples of 3 in [1,300], B = multiples of 5, C = multiples of 7.

n(A) = ⌊300/3⌋ = 100 n(B) = ⌊300/5⌋ = 60 n(C) = ⌊300/7⌋ = 42

n(A ∩ B) = multiples of 15: ⌊300/15⌋ = 20 n(B ∩ C) = multiples of 35: ⌊300/35⌋ = 8 n(A ∩ C) = multiples of 21: ⌊300/21⌋ = 14 n(A ∩ B ∩ C) = multiples of 105: ⌊300/105⌋ = 2

n(A ∪ B ∪ C) = 100 + 60 + 42 − 20 − 8 − 14 + 2 = 162

---

Problem 9 (Derangement connection): How many integers from 1 to 100 are NOT divisible by any of 2, 3, or 5?

Solution: A = multiples of 2: 50 B = multiples of 3: 33 C = multiples of 5: 20 A ∩ B = multiples of 6: 16 B ∩ C = multiples of 15: 6 A ∩ C = multiples of 10: 10 A ∩ B ∩ C = multiples of 30: 3

n(A ∪ B ∪ C) = 50 + 33 + 20 − 16 − 6 − 10 + 3 = 74

Not divisible by any = 100 − 74 = 26

(These are numbers coprime to 30 in [1,100]. Euler's totient function gives φ(30) = 8 numbers coprime to 30 in [1,30]. In [1,100] = 3 full cycles plus [91,100]: 3×8 + additional count... let's verify our direct count: the 26 numbers are 1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, 73, 77, 79, 83, 89, 91, 97. Count: 26 ✓)

---

Problem 10 (JEE Advanced 2015 type): Let n(U) = 700, n(A) = 200, n(B) = 300, n(A ∩ B) = 100. Find n(A' ∩ B').

Solution: n(A' ∩ B') = n((A ∪ B)') [De Morgan's] = n(U) − n(A ∪ B) = 700 − (200 + 300 − 100) = 700 − 400 = 300

---

Problem 11: A survey of 500 TV viewers shows:

• 285 watch Cricket
• 195 watch Hockey
• 115 watch Tennis
• 45 watch Cricket and Hockey
• 70 watch Cricket and Tennis
• 50 watch Hockey and Tennis
• 50 watch none

Find those who watch all three. Find those who watch exactly one sport.

Solution: Those watching at least one = 500 − 50 = 450.

450 = 285 + 195 + 115 − 45 − 70 − 50 + g 450 = 595 − 165 + g = 430 + g g = 20

Fill regions:

• Cricket ∩ Hockey only = 45 − 20 = 25
• Cricket ∩ Tennis only = 70 − 20 = 50
• Hockey ∩ Tennis only = 50 − 20 = 30
• Cricket only = 285 − 25 − 50 − 20 = 190
• Hockey only = 195 − 25 − 30 − 20 = 120
• Tennis only = 115 − 50 − 30 − 20 = 15

Exactly one: 190 + 120 + 15 = 325

---

Problem 12 (Structural — JEE Advanced): If A, B, C are three sets such that A ∩ B = A ∩ C and A ∪ B = A ∪ C, prove that B = C.

Solution: B = B ∩ (A ∪ B) [since B ⊆ A ∪ B, so B ∩ (A ∪ B) = B] = B ∩ (A ∪ C) [given A ∪ B = A ∪ C] = (B ∩ A) ∪ (B ∩ C) [distributive] = (A ∩ C) ∪ (B ∩ C) [given A ∩ B = A ∩ C, so B ∩ A = A ∩ B = A ∩ C] = (A ∪ B) ∩ C [distributive, factoring out C] = (A ∪ C) ∩ C [given A ∪ B = A ∪ C] = C [absorption: (A ∪ C) ∩ C = C]

Therefore B = C. □

This problem requires knowing absorption and being willing to apply the given hypotheses as substitutions. The move is: rewrite B using identities until you can substitute the hypotheses and simplify to C.

---

The Principle in Counting Theory

Inclusion-exclusion is a general principle of combinatorics, not just for sets. It shows up in:

• Derangements (permutations with no fixed point): D(n) = n! · Σ (−1)^k / k!
• Euler's totient function φ(n): count of integers ≤ n coprime to n
• Chromatic polynomials in graph theory
• Möbius inversion in number theory

All are applications of the same alternating-sum structure.

---

Summary

Formula	Statement
Two sets	n(A ∪ B) = n(A) + n(B) − n(A ∩ B)
Three sets	n(A∪B∪C) = n(A)+n(B)+n(C) − n(A∩B)−n(B∩C)−n(A∩C) + n(A∩B∩C)
Complement	n(A') = n(U) − n(A)
De Morgan	n(A'∩B') = n(U) − n(A∪B)

The working strategy:

1. Label the 8 regions of the three-set Venn diagram.
2. Fill from the inside out (triple intersection first, then pairwise, then single).
3. Use complement to find "none."
4. Sum appropriate regions for the specific question asked.

Next: File 04 continues with harder combinatorial problems using sets, number theory applications of inclusion-exclusion, and JEE Advanced problems on set counting.