Nguyên lý bù trừ là công thức đếm số phần tử của hợp nhiều tập khi các tập chồng lên nhau: cộng số phần tử của từng tập, trừ đi phần giao của từng cặp, cộng lại phần giao của từng bộ ba, và cứ xen kẽ như vậy. Với hai tập: |A ∪ B| = |A| + |B| − |A ∩ B|. Với ba tập: |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|.
Công thức hai tập ai cũng thấy hiển nhiên; từ ba tập trở đi, nhiều người bắt đầu thuộc vẹt dấu cộng trừ. Bài giải thích vì sao các dấu xen kẽ, đi qua ví dụ đếm số chia hết, hàm phi Euler, bài toán xếp thư sai địa chỉ với con số 1/e nổi tiếng, và cách dùng AI để kiểm những phép đếm rất dễ lệch này.
Hai tập và ba tập: vì sao phải trừ rồi lại cộng
Ví dụ giả định: một lớp 40 sinh viên, 25 bạn học thêm Python, 18 bạn học thêm SQL, 10 bạn học cả hai. Số bạn học ít nhất một môn không phải 25 + 18 = 43, vì 10 bạn học cả hai đã bị đếm hai lần, một lần trong nhóm Python và một lần trong nhóm SQL. Trừ đi phần đếm thừa: 43 − 10 = 33. Số bạn không học thêm môn nào là 40 − 33 = 7.
Với ba tập, lập luận theo từng vùng của biểu đồ Venn. Một phần tử thuộc đúng một tập được cộng một lần ở bước đầu, không bị trừ, đúng. Phần tử thuộc đúng hai tập được cộng hai lần, rồi bị trừ một lần ở bước giao từng cặp, còn một, đúng. Phần tử thuộc cả ba tập được cộng ba lần ở bước đầu, bị trừ ba lần ở bước giao từng cặp vì nó nằm trong cả ba giao cặp, về không, nên phải cộng lại một lần ở bước giao bộ ba. Dấu xen kẽ không phải quy ước mà là kết quả của việc sửa đếm thừa rồi sửa đếm thiếu.
Lập luận tổng quát dùng nhị thức: một phần tử thuộc đúng m tập sẽ được cộng m lần, trừ C(m, 2) lần, cộng C(m, 3) lần, và cứ thế. Tổng m − C(m, 2) + C(m, 3) − … bằng 1 với mọi m từ 1 trở lên, vì 1 − m + C(m, 2) − C(m, 3) + … chính là (1 − 1) mũ m, bằng 0. Đây là chứng minh gọn nhất, và cũng là lý do công thức đúng cho bất kỳ số tập nào.
Ví dụ từng bước: đếm số chia hết cho 2, 3 hoặc 5
Bài: từ 1 đến 100 có bao nhiêu số chia hết cho ít nhất một trong ba số 2, 3, 5? Gọi A, B, C lần lượt là tập các số chia hết cho 2, cho 3, cho 5.
- Đếm từng tập bằng phần nguyên của phép chia: |A| = 50, |B| = 33 vì 100 chia 3 được 33 dư 1, |C| = 20.
- Đếm giao từng cặp. Chia hết cho cả 2 và 3 là chia hết cho 6: có 16 số. Chia hết cho 10: có 10 số. Chia hết cho 15: có 6 số.
- Đếm giao cả ba, tức chia hết cho 30: có 3 số là 30, 60, 90.
- Ghép công thức: 50 + 33 + 20 − 16 − 10 − 6 + 3 = 74.
- Suy ra phần bù: số từ 1 đến 100 không chia hết cho 2, 3, 5 là 100 − 74 = 26. Kiểm nhanh trên dải nhỏ: trong 30 số đầu, các số như vậy là 1, 7, 11, 13, 17, 19, 23, 29, đúng 8 số, khớp với công thức áp cho 30.
Bước hai có một bẫy: giao của “chia hết cho 4” và “chia hết cho 6” là “chia hết cho 12”, không phải 24. Giao ứng với bội chung nhỏ nhất, chỉ bằng tích khi các số nguyên tố cùng nhau. Đây là lỗi mà cả người lẫn chatbot đều hay mắc khi đề đổi sang những số không nguyên tố.
Hàm phi Euler: bù trừ trong lý thuyết số
Hàm phi Euler φ(n) đếm số các số từ 1 đến n nguyên tố cùng nhau với n. Đây là đại lượng nền của hệ mã khoá công khai RSA, và cách tính nó là một ứng dụng trực tiếp của nguyên lý bù trừ. Với n = 30 = 2 × 3 × 5, các số không nguyên tố cùng nhau với 30 là những số chia hết cho 2, 3 hoặc 5. Áp đúng quy trình mục trước cho dải 1 đến 30: 15 + 10 + 6 − 5 − 3 − 2 + 1 = 22 số, nên φ(30) = 30 − 22 = 8.
Viết gọn lại, phép bù trừ cho φ(n) rút thành công thức tích: φ(n) bằng n nhân với (1 − 1/p) cho mỗi ước nguyên tố p của n. Với 30: 30 × 1/2 × 2/3 × 4/5 = 8, khớp. Với n = 12 = 2 mũ 2 × 3: 12 × 1/2 × 2/3 = 4, ứng với bốn số 1, 5, 7, 11. Lưu ý công thức chỉ dùng các ước nguyên tố khác nhau; số mũ không xuất hiện trong các thừa số.
Vì sao bù trừ lại cho ra một tích gọn như vậy? Vì với các số nguyên tố khác nhau, “chia hết cho p” và “chia hết cho q” độc lập theo nghĩa đếm trên dải 1 đến n: tỷ lệ số chia hết cho cả hai đúng bằng tích hai tỷ lệ. Khi đó khai triển tích (1 − a)(1 − b)(1 − c) ra đúng dãy cộng trừ của nguyên lý bù trừ. Nhận xét này cũng là cầu nối sang xác suất: công thức bù trừ cho xác suất của hợp các biến cố có dạng hoàn toàn tương tự.
Bài toán xếp thư sai địa chỉ và con số 1/e
Bài toán: n lá thư viết cho n người, cho vào n phong bì đã ghi địa chỉ một cách ngẫu nhiên. Có bao nhiêu cách để không lá thư nào vào đúng phong bì? Mỗi cách như vậy là một hoán vị không có điểm cố định, số lượng ký hiệu D(n). Gọi Ai là tập hoán vị mà thư thứ i vào đúng chỗ: giao của j tập bất kỳ có (n − j)! hoán vị, và có C(n, j) cách chọn j tập, nên D(n) = n! − C(n, 1)(n − 1)! + C(n, 2)(n − 2)! − … , rút gọn thành n! nhân (1 − 1/1! + 1/2! − 1/3! + … ± 1/n!).
| n | Số hoán vị n! | Số cách sai hết D(n) | Tỷ lệ D(n)/n! |
|---|---|---|---|
| 1 | 1 | 0 | 0 |
| 2 | 2 | 1 | 0,5 |
| 3 | 6 | 2 | khoảng 0,333 |
| 4 | 24 | 9 | 0,375 |
| 5 | 120 | 44 | khoảng 0,367 |
| 6 | 720 | 265 | khoảng 0,368 |
Tỷ lệ hội tụ rất nhanh về 1/e, khoảng 0,3679, vì chuỗi trong ngoặc chính là khai triển của e mũ −1. Kết quả phản trực giác: dù có 5 lá hay 5.000 lá thư, xác suất không lá nào đúng chỗ gần như không đổi, quanh 37 phần trăm. Kiểm tay với n = 3: các hoán vị của 1, 2, 3 không giữ phần tử nào tại chỗ là 2, 3, 1 và 3, 1, 2, đúng 2 cách.
Ứng dụng đời thường kiểu bốc thăm tặng quà cuối năm, ví dụ giả định: 30 người bỏ tên vào hộp rồi mỗi người bốc một tên, xác suất không ai bốc trúng tên mình là khoảng 37 phần trăm, nghĩa là khoảng 63 phần trăm số lần tổ chức sẽ có ít nhất một người phải bốc lại.
Những lỗi hay gặp khi áp nguyên lý bù trừ
Quên một số hạng giao. Với bốn tập có 6 giao cặp, 4 giao bộ ba và 1 giao bộ bốn, cộng với 4 tập đơn là 15 số hạng. Liệt kê theo hệ thống, ví dụ theo thứ tự từ điển AB, AC, AD, BC, BD, CD, để không sót.
Tính giao bằng tích khi không được phép. Như bẫy bội chung nhỏ nhất ở trên, hoặc khi các tập không độc lập. Luôn định nghĩa lại giao bằng lời trước khi đếm.
Nhầm “ít nhất một” với “đúng một”. Nguyên lý bù trừ cho số phần tử thuộc ít nhất một tập. Số phần tử thuộc đúng một trong ba tập cần công thức khác: tổng ba tập, trừ hai lần tổng các giao cặp, cộng ba lần giao bộ ba.
Dùng bù trừ khi đếm phần bù trực tiếp dễ hơn. Hỏi “có bao nhiêu số từ 0 đến 999 có ít nhất một chữ số 7” thì đếm phần bù nhanh hơn nhiều: viết mỗi số thành ba chữ số, số không có chữ số 7 là 9 mũ 3 = 729, nên đáp số là 1.000 − 729 = 271.
Không kiểm bằng trường hợp nhỏ. Bất kỳ công thức bù trừ nào cũng nên thử với một dải số nhỏ có thể liệt kê tay. Lệch ở trường hợp nhỏ là sai ở trường hợp lớn.
Dùng AI kiểm bài bù trừ mà không chép lời giải
Bài bù trừ có nhiều số hạng, nên chỗ sai thường nằm ở một con số giao bị tính lệch chứ không ở ý tưởng. Chatbot hay mắc đúng loại lỗi này: chọn công thức đúng rồi chia sai một phép lấy phần nguyên. Quy trình kiểm:
- Tự viết bảng các tập và các giao cần đếm, mỗi dòng một số hạng kèm dấu, trước khi điền số.
- Nhờ AI kiểm danh sách số hạng, chưa kiểm số. Câu lệnh mẫu: “Mình đếm hợp của bốn tập bằng nguyên lý bù trừ. Đây là danh sách các số hạng giao mình định tính, kèm dấu. Có thiếu hay thừa số hạng nào không?”
- Tự điền số, rồi nhờ AI viết một đoạn chương trình duyệt từ 1 đến N và đếm trực tiếp. Chạy trên máy của bạn và so hai kết quả.
- Nếu lệch, chạy lại chương trình cho riêng từng giao để tìm số hạng sai, thay vì sửa đáp số cuối.
- Với bài xác suất dạng bốc thăm, mô phỏng vài chục nghìn lần bằng chương trình để thấy tỷ lệ quanh con số lý thuyết. Mô phỏng không thay chứng minh nhưng bắt lỗi dấu rất nhanh.
Nếu dữ liệu cần đếm là dữ liệu thật của đơn vị bạn, ví dụ danh sách khách mua nhiều nhóm sản phẩm, chỉ đưa vào AI các con số tổng hợp hoặc mã hoá tên, không dán danh sách có thông tin cá nhân.
Câu hỏi thường gặp
Nguyên lý bù trừ và biểu đồ Venn khác nhau thế nào?
Biểu đồ Venn là hình vẽ minh hoạ các vùng giao nhau, rất tiện với hai hoặc ba tập. Nguyên lý bù trừ là công thức đúng với số tập bất kỳ. Từ bốn tập trở lên, biểu đồ vẽ bằng hình tròn không còn thể hiện đủ mọi vùng giao, nên phải dựa vào công thức.
Có cần thuộc công thức xếp thư sai địa chỉ không?
Không cần thuộc dạng chuỗi, chỉ cần nhớ cách suy ra bằng bù trừ và hệ thức truy hồi D(n) = (n − 1)(D(n − 1) + D(n − 2)). Với D(1) = 0 và D(2) = 1, hệ thức cho D(3) = 2, D(4) = 9, D(5) = 44, đủ để kiểm mọi bài nhỏ.
Nguyên lý bù trừ dùng trong xác suất như thế nào?
Công thức có dạng y hệt, chỉ thay số phần tử bằng xác suất: P(A hoặc B) = P(A) + P(B) − P(A và B), và tương tự cho nhiều biến cố. Khi các xác suất giao khó tính, người ta dùng bất đẳng thức Bonferroni, tức dừng khai triển ở một bước để được cận trên hoặc cận dưới.
Khi có quá nhiều tập thì bù trừ còn dùng được không?
Với n tập, số số hạng là 2 mũ n trừ 1, nên khi n lớn công thức chỉ khả thi nếu các giao có quy luật đối xứng, như trong bài xếp thư sai địa chỉ, nơi mọi giao j tập đều có cùng kích thước. Không có đối xứng thì thường phải tìm cách khác như hệ thức truy hồi hay quy hoạch động.
Có phải bài đếm nào có chữ “ít nhất một” cũng dùng bù trừ?
Không nhất thiết. Nhiều bài “ít nhất một” giải nhanh hơn bằng cách đếm phần bù, tức đếm số trường hợp “không có cái nào” rồi lấy tổng trừ đi. Bù trừ cần khi chính phần bù cũng là hợp của nhiều điều kiện chồng nhau, không đếm thẳng được.