Nguyên Lý Bù Trừ (Inclusion-Exclusion) - Đếm Số Phần Tử Hợp Các Tập Hợp

1. Giới thiệu

Nguyên lý bù trừ là một công cụ mạnh mẽ trong toán học tổ hợp, giúp ta đếm số phần tử của hợp các tập hợp khi biết số phần tử của từng tập hợp và các giao của chúng. Nguyên lý này đặc biệt hữu ích khi các tập hợp có sự giao nhau, khiến việc đếm trực tiếp trở nên khó khăn.

2. Nguyên lý bù trừ cho hai tập hợp

2.1. Phát biểu

Cho hai tập hợp hữu hạn $A$ và $B$. Khi đó, số phần tử của hợp hai tập hợp $A \cup B$ được tính bởi công thức:

$|A \cup B| = |A| + |B| - |A \cap B|$

2.2. Giải thích trực quan

Ta có thể dễ dàng hình dung công thức trên bằng sơ đồ Venn. Khi cộng $|A|$ và $|B|$, các phần tử thuộc giao $A \cap B$ bị đếm hai lần. Do đó, ta cần trừ đi $|A \cap B|$ để có số phần tử chính xác của $A \cup B$.

2.3. Ví dụ

Ví dụ 1: Trong một lớp học có 30 học sinh, có 20 học sinh thích môn Toán, 15 học sinh thích môn Văn và 8 học sinh thích cả hai môn. Hỏi có bao nhiêu học sinh thích ít nhất một trong hai môn Toán hoặc Văn?

Giải:

Gọi $A$ là tập hợp các học sinh thích môn Toán, $B$ là tập hợp các học sinh thích môn Văn. Theo đề bài, ta có:

• $|A| = 20$
• $|B| = 15$
• $|A \cap B| = 8$

Số học sinh thích ít nhất một trong hai môn là $|A \cup B|$. Áp dụng công thức nguyên lý bù trừ cho hai tập hợp:

$|A \cup B| = |A| + |B| - |A \cap B| = 20 + 15 - 8 = 27$

Vậy có 27 học sinh thích ít nhất một trong hai môn Toán hoặc Văn.

3. Nguyên lý bù trừ cho ba tập hợp

3.1. Phát biểu

Cho ba tập hợp hữu hạn $A$, $B$ và $C$. Khi đó, số phần tử của hợp ba tập hợp $A \cup B \cup C$ được tính bởi công thức:

$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$

3.2. Giải thích trực quan

Tương tự như trường hợp hai tập hợp, ta có thể hình dung công thức này bằng sơ đồ Venn.

• Khi cộng $|A| + |B| + |C|$, các phần tử thuộc giao của hai tập hợp bị đếm hai lần, các phần tử thuộc giao của ba tập hợp bị đếm ba lần.
• Để khắc phục điều này, ta trừ đi $|A \cap B| + |A \cap C| + |B \cap C|$. Tuy nhiên, khi đó các phần tử thuộc $A \cap B \cap C$ lại bị trừ đi ba lần (do bị đếm ba lần và trừ ba lần).
• Do đó, ta cần cộng lại $|A \cap B \cap C|$ để có số phần tử chính xác của $A \cup B \cup C$.

3.3. Ví dụ

Ví dụ 2: Trong một cuộc khảo sát 100 người về sở thích đọc sách, người ta thu được kết quả như sau:

• 40 người thích đọc tiểu thuyết.
• 30 người thích đọc truyện ngắn.
• 25 người thích đọc thơ.
• 15 người thích đọc cả tiểu thuyết và truyện ngắn.
• 10 người thích đọc cả tiểu thuyết và thơ.
• 8 người thích đọc cả truyện ngắn và thơ.
• 5 người thích đọc cả ba thể loại.

Hỏi có bao nhiêu người thích đọc ít nhất một trong ba thể loại trên?

Giải:

Gọi $A$ là tập hợp những người thích đọc tiểu thuyết, $B$ là tập hợp những người thích đọc truyện ngắn, $C$ là tập hợp những người thích đọc thơ. Theo đề bài, ta có:

• $|A| = 40$
• $|B| = 30$
• $|C| = 25$
• $|A \cap B| = 15$
• $|A \cap C| = 10$
• $|B \cap C| = 8$
• $|A \cap B \cap C| = 5$

Số người thích đọc ít nhất một trong ba thể loại là $|A \cup B \cup C|$. Áp dụng công thức nguyên lý bù trừ cho ba tập hợp:

$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$ $|A \cup B \cup C| = 40 + 30 + 25 - 15 - 10 - 8 + 5 = 67$

Vậy có 67 người thích đọc ít nhất một trong ba thể loại trên.

4. Nguyên lý bù trừ tổng quát

4.1. Phát biểu

Cho $n$ tập hợp hữu hạn $A_1, A_2, ..., A_n$. Khi đó, số phần tử của hợp $n$ tập hợp $A_1 \cup A_2 \cup ... \cup A_n$ được tính bởi công thức:

$|A_1 \cup A_2 \cup ... \cup A_n| = \sum_{i=1}^{n} |A_i| - \sum_{1 \le i < j \le n} |A_i \cap A_j| + \sum_{1 \le i < j < k \le n} |A_i \cap A_j \cap A_k| - ... + (-1)^{n-1} |A_1 \cap A_2 \cap ... \cap A_n|$

4.2. Giải thích công thức

Công thức trên có thể được viết gọn lại như sau:

$|A_1 \cup A_2 \cup ... \cup A_n| = \sum_{k=1}^{n} (-1)^{k-1} \left( \sum_{1 \le i_1 < i_2 < ... < i_k \le n} |A_{i_1} \cap A_{i_2} \cap ... \cap A_{i_k}| \right)$

Trong đó:

• $\sum_{i=1}^{n} |A_i|$ là tổng số phần tử của từng tập hợp.
• $\sum_{1 \le i < j \le n} |A_i \cap A_j|$ là tổng số phần tử của giao hai tập hợp.
• $\sum_{1 \le i < j < k \le n} |A_i \cap A_j \cap A_k|$ là tổng số phần tử của giao ba tập hợp.
• ...
• $|A_1 \cap A_2 \cap ... \cap A_n|$ là số phần tử của giao của tất cả $n$ tập hợp.

Dấu $(-1)^{k-1}$ đảm bảo việc cộng hoặc trừ đúng số phần tử của giao của $k$ tập hợp.

4.3. Ví dụ

Ví dụ 3: Có 100 sinh viên tham gia ba câu lạc bộ: Âm nhạc, Thể thao và Văn học. Biết rằng:

• 50 sinh viên tham gia câu lạc bộ Âm nhạc.
• 40 sinh viên tham gia câu lạc bộ Thể thao.
• 30 sinh viên tham gia câu lạc bộ Văn học.
• 20 sinh viên tham gia cả Âm nhạc và Thể thao.
• 15 sinh viên tham gia cả Âm nhạc và Văn học.
• 10 sinh viên tham gia cả Thể thao và Văn học.
• 5 sinh viên tham gia cả ba câu lạc bộ.

Hỏi có bao nhiêu sinh viên tham gia ít nhất một câu lạc bộ?

Giải:

Gọi $A$ là tập hợp sinh viên tham gia câu lạc bộ Âm nhạc, $B$ là tập hợp sinh viên tham gia câu lạc bộ Thể thao, $C$ là tập hợp sinh viên tham gia câu lạc bộ Văn học. Theo đề bài, ta có:

• $|A| = 50$
• $|B| = 40$
• $|C| = 30$
• $|A \cap B| = 20$
• $|A \cap C| = 15$
• $|B \cap C| = 10$
• $|A \cap B \cap C| = 5$

Số sinh viên tham gia ít nhất một câu lạc bộ là $|A \cup B \cup C|$. Áp dụng công thức nguyên lý bù trừ cho ba tập hợp:

$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$ $|A \cup B \cup C| = 50 + 40 + 30 - 20 - 15 - 10 + 5 = 80$

Vậy có 80 sinh viên tham gia ít nhất một câu lạc bộ.

5. Ứng dụng của nguyên lý bù trừ

Nguyên lý bù trừ có nhiều ứng dụng trong các bài toán đếm, đặc biệt là trong các bài toán liên quan đến tổ hợp và xác suất. Một số ứng dụng phổ biến bao gồm:

• Đếm số nghiệm nguyên của phương trình: Nguyên lý bù trừ có thể được sử dụng để đếm số nghiệm nguyên của phương trình thỏa mãn một số điều kiện cho trước.
• Đếm số số tự nhiên thỏa mãn một số tính chất: Ví dụ, đếm số số tự nhiên nhỏ hơn $n$ không chia hết cho bất kỳ số nào trong tập hợp $\{p_1, p_2, ..., p_k\}$.
• Bài toán về hàm số toàn ánh: Nguyên lý bù trừ được sử dụng để đếm số hàm toàn ánh từ một tập hợp $A$ có $m$ phần tử vào một tập hợp $B$ có $n$ phần tử.

6. Bài tập vận dụng

Bài 1: Có bao nhiêu số tự nhiên nhỏ hơn 1000 chia hết cho 2 hoặc 3?

Bài 2: Có bao nhiêu số tự nhiên nhỏ hơn 1000 không chia hết cho 2, 3 hoặc 5?

Bài 3: Một lớp học có 40 học sinh, trong đó có 25 học sinh giỏi Toán, 20 học sinh giỏi Lý, 15 học sinh giỏi Hóa. Có 12 học sinh giỏi cả Toán và Lý, 10 học sinh giỏi cả Toán và Hóa, 8 học sinh giỏi cả Lý và Hóa. Có 5 học sinh giỏi cả ba môn. Hỏi có bao nhiêu học sinh không giỏi môn nào?

Bài 4: Cho tập hợp $A = \{1, 2, ..., 100\}$. Hỏi có bao nhiêu số trong $A$ không chia hết cho 2, 3 hoặc 5?

Bài 5: Có bao nhiêu số có 5 chữ số mà trong đó không có chữ số 0, 1, 2?

7. Kết luận

Nguyên lý bù trừ là một công cụ hữu ích và mạnh mẽ trong toán học tổ hợp. Việc nắm vững nguyên lý này sẽ giúp bạn giải quyết nhiều bài toán đếm một cách hiệu quả. Hy vọng tài liệu này sẽ giúp bạn hiểu rõ hơn về nguyên lý bù trừ và ứng dụng nó vào giải toán.