Phần

Bẫy đếm trùng

Mục tiêu

Sau bài học này, em áp dụng thành thạo nguyên lý bù trừ đơn giản ( $|A\cup B|=|A|+|B|-|A\cap B|$ ) để đếm đúng khi hai tập hợp giao nhau, và biết dùng phần bù để đếm nhanh số đối tượng KHÔNG thuộc cả hai tập cùng lúc.

Sau bài học này, em áp dụng thành thạo **nguyên lý bù trừ đơn giản** ($|A\cup B|=|A|+|B|-|A\cap B|$) để đếm đúng khi hai tập hợp giao nhau, và biết dùng phần bù để đếm nhanh số đối tượng KHÔNG thuộc cả hai tập cùng lúc.

Kiến thức cần có trước

Bài này dùng lại quy tắc cộng/nhân vừa học ở Bài 1. Mở rộng dành cho HSG: ký hiệu $|A\cup B|=|A|+|B|-|A\cap B|$ (nguyên lý bù trừ cho hai tập hợp) không nằm trong yêu cầu cần đạt chuẩn Lớp 8 — bài học giới thiệu công thức này như một cách viết gọn của "cộng rồi trừ phần giao" đã thấy ở Ví dụ 3 bài trước, không đòi hỏi kiến thức tập hợp nào xa hơn.

Bài này dùng lại quy tắc cộng/nhân vừa học ở Bài 1. **Mở rộng dành cho HSG**: ký hiệu $|A\cup B|=|A|+|B|-|A\cap B|$ (nguyên lý bù trừ cho hai tập hợp) không nằm trong yêu cầu cần đạt chuẩn Lớp 8 — bài học giới thiệu công thức này như một cách viết gọn của "cộng rồi trừ phần giao" đã thấy ở Ví dụ 3 bài trước, không đòi hỏi kiến thức tập hợp nào xa hơn.

Khởi động

Câu hỏi mở đầu

Từ 1 đến 100, có bao nhiêu số chia hết cho 3 hoặc chia hết cho 7? Nếu chỉ đếm số chia hết cho 3 (33 số) rồi cộng số chia hết cho 7 (14 số), em có tin kết quả 47 là đúng không? Thử liệt kê vài số như 21 — nó chia hết cho cả 3 và 7, vậy nó đã bị đếm bao nhiêu lần trong 47?

Ý tưởng chính: đếm phần giao đúng một lần

Cái khó không nằm ở công thức, mà ở việc tính đúng $|A\cap B|$ : tập giao của "chia hết cho 3" và "chia hết cho 7" chính là tập "chia hết cho $3\times 7=21$ " — vì một số chia hết cho cả 3 và 7 khi và chỉ khi nó chia hết cho bội chung nhỏ nhất của chúng. Với hai số nguyên tố cùng nhau, bội chung nhỏ nhất bằng tích của chúng; nếu không nguyên tố cùng nhau (như 4 và 6), phải tính bội chung nhỏ nhất thật sự chứ không được nhân thẳng hai số lại.

Công thức này còn mở ra một hướng đếm khác: đếm phần KHÔNG thuộc cả hai tập, bằng cách lấy tổng thể trừ đi $|A\cup B|$ . Đây chính là đếm bằng phần bù kết hợp bù trừ — kỹ thuật sẽ được đào sâu riêng ở Bài 2 Chương 3, nhưng ta làm quen ngay từ đây qua Ví dụ 3.

Ví dụ 3 của bài trước đã cho thấy: khi hai nhóm giao nhau, cộng thẳng số lượng của chúng sẽ đếm phần giao hai lần. Bài này viết lại quan sát đó thành một công thức dùng được cho mọi bài toán tương tự: gọi $A$ là tập các số chia hết cho 3, $B$ là tập các số chia hết cho 7, thì số phần tử thuộc $A$ hoặc $B$ là $|A\cup B|=|A|+|B|-|A\cap B|$ — cộng hai tập rồi trừ đúng một lần phần giao đã bị đếm thừa. Cái khó không nằm ở công thức, mà ở việc tính đúng $|A\cap B|$: tập giao của "chia hết cho 3" và "chia hết cho 7" chính là tập "chia hết cho $3\times 7=21$" — vì một số chia hết cho cả 3 và 7 khi và chỉ khi nó chia hết cho bội chung nhỏ nhất của chúng. Với hai số nguyên tố cùng nhau, bội chung nhỏ nhất bằng tích của chúng; nếu không nguyên tố cùng nhau (như 4 và 6), phải tính bội chung nhỏ nhất thật sự chứ không được nhân thẳng hai số lại. Công thức này còn mở ra một hướng đếm khác: đếm phần KHÔNG thuộc cả hai tập, bằng cách lấy tổng thể trừ đi $|A\cup B|$. Đây chính là đếm bằng phần bù kết hợp bù trừ — kỹ thuật sẽ được đào sâu riêng ở Bài 2 Chương 3, nhưng ta làm quen ngay từ đây qua Ví dụ 3.

Ví dụ áp dụng

Ví dụ

Đếm phần tử của hai tập giao nhau

1
Từ 1 đến 100, đếm các số chia hết cho 3 hoặc chia hết cho 7. Tập $A$ (chia hết cho 3) có $\lfloor 100/3\rfloor=33$ phần tử. (1) Tập $B$ (chia hết cho 7) có $\lfloor 100/7\rfloor=14$ phần tử. (2) Vì $3$ và $7$ nguyên tố cùng nhau, tập giao (chia hết cho $21$ ) có $\lfloor 100/21\rfloor=4$ phần tử. (3)
Từ 1 đến 100, đếm các số chia hết cho 3 hoặc chia hết cho 7. Tập $A$ (chia hết cho 3) có $\lfloor 100/3\rfloor=33$ phần tử. (1) Tập $B$ (chia hết cho 7) có $\lfloor 100/7\rfloor=14$ phần tử. (2) Vì $3$ và $7$ nguyên tố cùng nhau, tập giao (chia hết cho $21$) có $\lfloor 100/21\rfloor=4$ phần tử. (3)
2
Kết hợp (1), (2) và (3): $|A\cup B|=33+14-4=43$ . Vậy có $43$ số từ 1 đến 100 chia hết cho 3 hoặc chia hết cho 7.
Kết hợp (1), (2) và (3): $|A\cup B|=33+14-4=43$. Vậy có $43$ số từ 1 đến 100 chia hết cho 3 hoặc chia hết cho 7.

Ví dụ

Đếm phần bù trong bài toán câu lạc bộ

1
Một câu lạc bộ có 30 thành viên. Có 12 bạn tham gia đội bóng đá, 10 bạn tham gia đội cầu lông, 5 bạn tham gia CẢ HAI đội. Hỏi có bao nhiêu bạn KHÔNG tham gia đội nào?
2
Áp dụng công thức bù trừ với $|A|=12$ , $|B|=10$ , $|A\cap B|=5$ : $|A\cup B|=12+10-5=17$ bạn tham gia ít nhất một đội. (1)
Áp dụng công thức bù trừ với $|A|=12$, $|B|=10$, $|A\cap B|=5$: $|A\cup B|=12+10-5=17$ bạn tham gia ít nhất một đội. (1)
3
Theo (1), số bạn không tham gia đội nào là $30-17=13$ . Vậy có $13$ bạn trong câu lạc bộ không tham gia đội bóng đá lẫn đội cầu lông.
Theo (1), số bạn không tham gia đội nào là $30-17=13$. Vậy có $13$ bạn trong câu lạc bộ không tham gia đội bóng đá lẫn đội cầu lông.

Bước 3 là bước hay bị bỏ sót nhất khi hai tập không thực sự rời nhau.

Ví dụ

Kết hợp bù trừ với đếm bằng phần bù

1
Từ 1 đến 60, đếm các số KHÔNG chia hết cho 3 VÀ KHÔNG chia hết cho 4. Đây là phủ định của hai điều kiện cùng lúc, nên ta đếm phần thuộc ít nhất một tập rồi lấy phần bù trên tổng thể.
2
Chia hết cho 3: $\lfloor 60/3\rfloor=20$ . (1) Chia hết cho 4: $\lfloor 60/4\rfloor=15$ . (2) Chia hết cho cả 3 và 4 (tức chia hết cho 12, vì $3{,}4$ nguyên tố cùng nhau): $\lfloor 60/12\rfloor=5$ . (3)
Chia hết cho 3: $\lfloor 60/3\rfloor=20$. (1) Chia hết cho 4: $\lfloor 60/4\rfloor=15$. (2) Chia hết cho cả 3 và 4 (tức chia hết cho 12, vì $3,4$ nguyên tố cùng nhau): $\lfloor 60/12\rfloor=5$. (3)
3
Kết hợp (1), (2) và (3): số chia hết cho 3 hoặc 4 là $20+15-5=30$ . Lấy phần bù trên tổng thể 60 số: $60-30=30$ . Vậy có $30$ số từ 1 đến 60 không chia hết cho 3 và không chia hết cho 4.
Kết hợp (1), (2) và (3): số chia hết cho 3 hoặc 4 là $20+15-5=30$. Lấy phần bù trên tổng thể 60 số: $60-30=30$. Vậy có $30$ số từ 1 đến 60 không chia hết cho 3 và không chia hết cho 4.

Sai lầm thường gặp

Bẫy thường gặp

Khi hai số chia hết không nguyên tố cùng nhau, nhiều bạn vẫn nhân thẳng hai số để tìm phần giao — ví dụ tính "chia hết cho 4 và 6" bằng cách chia cho $4\times 6=24$ là SAI, vì bội chung nhỏ nhất của 4 và 6 là 12, không phải 24. Luôn kiểm tra ước chung của hai số trước khi tìm bội chung nhỏ nhất.

Luyện tập có hướng dẫn

Luyện tập độc lập

Chốt lại

Nhớ công thức $|A\cup B|=|A|+|B|-|A\cap B|$ như một cách viết chính xác của "cộng rồi trừ phần giao", và luôn kiểm tra bội chung nhỏ nhất thật sự trước khi tính phần giao của hai điều kiện chia hết.

Chương tiếp theo chuyển sang một dạng đếm khác hẳn: đếm số đường đi trên lưới ô vuông, nơi nguyên lý cộng và nhân được dùng lồng vào nhau theo một cách rất tự nhiên.