Phần

Đếm bằng phần bù

Mục tiêu

Sau bài học này, em nhận ra khi nào nên đếm phần bù (đếm toàn bộ trừ đi phần không thỏa mãn) thay vì đếm trực tiếp, đặc biệt với các đề bài chứa cụm từ "ít nhất", "khác nhau tất cả", hay "không hoàn toàn".

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à tổ hợp $C_n^k$ đã ôn ở Bài 1. Ví dụ cuối còn giới thiệu nguyên lý bao hàm - loại trừ cho 2 tập hợp ( $|A\cup B|=|A|+|B|-|A\cap B|$ ) như một phần mở rộng dành cho HSG nhẹ -- đây không nằm trong YCCĐ chuẩn Lớp 9 nhưng là kỹ thuật phổ biến trong đề HSG đếm số.

Bài này dùng lại quy tắc cộng/nhân và tổ hợp $C_n^k$ đã ôn ở Bài 1. Ví dụ cuối còn giới thiệu **nguyên lý bao hàm - loại trừ** cho 2 tập hợp ($|A\cup B|=|A|+|B|-|A\cap B|$) như một phần mở rộng dành cho HSG nhẹ -- đây không nằm trong YCCĐ chuẩn Lớp 9 nhưng là kỹ thuật phổ biến trong đề HSG đếm số.

Khởi động: so sánh với cách làm trực tiếp

Câu hỏi mở đầu

Từ 5 nam, 4 nữ, chọn một ban cán sự 3 người có ít nhất 1 nữ. Nếu đếm trực tiếp, em phải chia 3 trường hợp: đúng 1 nữ, đúng 2 nữ, đúng 3 nữ -- rồi cộng lại. Có cách nào nhanh hơn không?

Ý tưởng chính: đếm bù

Vậy làm sao cho gọn? Nếu tập "KHÔNG thỏa mãn" đơn giản hơn hẳn tập "thỏa mãn", ta đếm tập không thỏa mãn rồi lấy hiệu: $\text{số cách thỏa mãn} = \text{tổng số cách} - \text{số cách KHÔNG thỏa mãn}.$ Với điều kiện "ít nhất 1 nữ" chẳng hạn, phần đối lập chỉ có ĐÚNG 1 trường hợp ("không có nữ nào", tức toàn nam) thay vì 3 trường hợp khi đếm trực tiếp -- đó là lý do đếm bù mạnh hơn hẳn ở đây.

Nhưng đếm bù không phải lúc nào cũng lợi. Nếu phần đối lập cũng phức tạp không kém phần cần đếm (ví dụ điều kiện "đúng 2 nữ" thay vì "ít nhất 1 nữ"), đếm bù chẳng giúp được gì -- lúc đó quay lại chia trường hợp trực tiếp như Bài 1 sẽ nhanh hơn. Công thức lấy hiệu thì quá đơn giản, cái khó thật sự -- cũng là kỹ năng quan trọng nhất của bài này -- là nhận ra được khi nào phần đối lập thực sự đơn giản hơn hẳn.

Đề thi thông thường hỏi trực tiếp kiểu "có bao nhiêu cách chọn 2 nữ 1 nam" -- một trường hợp đơn, tính thẳng ra kết quả. Nhưng khi đề bài có điều kiện phủ định hoặc "ít nhất", số trường hợp cần chia theo cách làm Bài 1 có thể lên tới 3, 4, thậm chí nhiều hơn -- càng chia nhiều trường hợp càng dễ đếm sót hoặc đếm trùng. Vậy làm sao cho gọn? Nếu tập "KHÔNG thỏa mãn" đơn giản hơn hẳn tập "thỏa mãn", ta đếm tập không thỏa mãn rồi lấy hiệu: $$\text{số cách thỏa mãn} = \text{tổng số cách} - \text{số cách KHÔNG thỏa mãn}.$$ Với điều kiện "ít nhất 1 nữ" chẳng hạn, phần đối lập chỉ có ĐÚNG 1 trường hợp ("không có nữ nào", tức toàn nam) thay vì 3 trường hợp khi đếm trực tiếp -- đó là lý do đếm bù mạnh hơn hẳn ở đây. Nhưng đếm bù không phải lúc nào cũng lợi. Nếu phần đối lập cũng phức tạp không kém phần cần đếm (ví dụ điều kiện "đúng 2 nữ" thay vì "ít nhất 1 nữ"), đếm bù chẳng giúp được gì -- lúc đó quay lại chia trường hợp trực tiếp như Bài 1 sẽ nhanh hơn. Công thức lấy hiệu thì quá đơn giản, cái khó thật sự -- cũng là kỹ năng quan trọng nhất của bài này -- là nhận ra được khi nào phần đối lập thực sự đơn giản hơn hẳn.

Ví dụ áp dụng

Ví dụ

Ban cán sự ít nhất 1 nữ

1
Từ $5$ nam, $4$ nữ ( $9$ người), chọn $3$ người làm ban cán sự, có ít nhất $1$ nữ. Tổng thể: chọn 3 từ 9 người bất kỳ, không điều kiện. Phần đối lập của "có ít nhất 1 nữ" là "không có nữ nào", tức "toàn là nam" -- chỉ một trường hợp duy nhất, đơn giản hơn nhiều so với việc chia 3 trường hợp (1 nữ, 2 nữ, 3 nữ).
Từ $5$ nam, $4$ nữ ($9$ người), chọn $3$ người làm ban cán sự, có ít nhất $1$ nữ. Tổng thể: chọn 3 từ 9 người bất kỳ, không điều kiện. Phần đối lập của "có ít nhất 1 nữ" là "không có nữ nào", tức "toàn là nam" -- chỉ một trường hợp duy nhất, đơn giản hơn nhiều so với việc chia 3 trường hợp (1 nữ, 2 nữ, 3 nữ).
2
$C_9^3=\dfrac{9!}{3!6!}=84$ cách chọn 3 người bất kỳ từ 9 người. (1)
$C_9^3=\dfrac{9!}{3!6!}=84$ cách chọn 3 người bất kỳ từ 9 người. (1)
3
Số cách chọn 3 người mà không có nữ nào (toàn nam), chọn từ 5 nam: $C_5^3=10$ cách. (2)
Số cách chọn 3 người mà không có nữ nào (toàn nam), chọn từ 5 nam: $C_5^3=10$ cách. (2)
4
Lấy hiệu (1) trừ (2): số cách có ít nhất 1 nữ là $84-10=74$ cách. So với cách đếm trực tiếp (phải tính $C_4^1 C_5^2 + C_4^2 C_5^1 + C_4^3$ rồi cộng 3 số hạng), đây nhanh và ít sai sót hơn hẳn. Vậy có $74$ cách chọn ban cán sự thỏa yêu cầu đề bài.
Lấy hiệu (1) trừ (2): số cách có ít nhất 1 nữ là $84-10=74$ cách. So với cách đếm trực tiếp (phải tính $C_4^1 C_5^2 + C_4^2 C_5^1 + C_4^3$ rồi cộng 3 số hạng), đây nhanh và ít sai sót hơn hẳn. Vậy có $74$ cách chọn ban cán sự thỏa yêu cầu đề bài.

Áp dụng khi phần "không thỏa mãn" đơn giản rõ rệt so với phần "thỏa mãn".

Ví dụ

Đếm bù trong bài toán xếp hàng

1
Xếp 6 bạn thành một hàng dọc sao cho 2 bạn A, B không đứng cạnh nhau. Tổng thể: xếp 6 bạn bất kỳ. Phần đối lập của "A, B không cạnh nhau" là "A, B đứng cạnh nhau".
2
Số cách xếp 6 bạn thành hàng bất kỳ: $6!=720$ . (1)
Số cách xếp 6 bạn thành hàng bất kỳ: $6!=720$. (1)
3
Coi A và B là một khối dính (buộc chùm), khối này có thể là "AB" hoặc "BA" (2 cách xếp nội bộ). Khối cùng 4 bạn còn lại tạo thành 5 đối tượng, xếp thành hàng: $5!$ cách. Tổng số cách A, B cạnh nhau: $5!\times 2=240$ . (2)
Coi A và B là một khối dính (buộc chùm), khối này có thể là "AB" hoặc "BA" (2 cách xếp nội bộ). Khối cùng 4 bạn còn lại tạo thành 5 đối tượng, xếp thành hàng: $5!$ cách. Tổng số cách A, B cạnh nhau: $5!\times 2=240$. (2)
4
Lấy hiệu (1) trừ (2): số cách A, B không cạnh nhau là $720-240=480$ . Vậy có $480$ cách xếp 6 bạn thành hàng thỏa mãn A, B không đứng cạnh nhau.
Lấy hiệu (1) trừ (2): số cách A, B không cạnh nhau là $720-240=480$. Vậy có $480$ cách xếp 6 bạn thành hàng thỏa mãn A, B không đứng cạnh nhau.

Ví dụ

Kết hợp bao hàm - loại trừ (Mở rộng dành cho HSG)

1
Từ $1$ đến $100$ , đếm các số KHÔNG chia hết cho $3$ VÀ KHÔNG chia hết cho $5$ . Đây là phủ định của 2 điều kiện cùng lúc -- nếu đếm trực tiếp sẽ rất phức tạp, nên dùng phần bù kết hợp bao hàm - loại trừ.
Từ $1$ đến $100$, đếm các số KHÔNG chia hết cho $3$ VÀ KHÔNG chia hết cho $5$. Đây là phủ định của 2 điều kiện cùng lúc -- nếu đếm trực tiếp sẽ rất phức tạp, nên dùng phần bù kết hợp bao hàm - loại trừ.
2
Ta có: số chia hết cho 3 từ 1-100 là $\lfloor 100/3\rfloor=33$ . (1) Số chia hết cho 5 là $\lfloor 100/5\rfloor=20$ . (2) Số chia hết cả 3 và 5 (tức chia hết 15) là $\lfloor 100/15\rfloor=6$ . (3)
Ta có: số chia hết cho 3 từ 1-100 là $\lfloor 100/3\rfloor=33$. (1) Số chia hết cho 5 là $\lfloor 100/5\rfloor=20$. (2) Số chia hết cả 3 và 5 (tức chia hết 15) là $\lfloor 100/15\rfloor=6$. (3)
3
Kết hợp (1), (2) và (3) theo nguyên lý bao hàm - loại trừ cho 2 tập: số chia hết cho 3 HOẶC 5 là $|A\cup B|=|A|+|B|-|A\cap B|=33+20-6=47$ (trừ phần giao để không đếm trùng những số vừa chia hết 3 vừa chia hết 5).
Kết hợp (1), (2) và (3) theo nguyên lý bao hàm - loại trừ cho 2 tập: số chia hết cho 3 HOẶC 5 là $|A\cup B|=|A|+|B|-|A\cap B|=33+20-6=47$ (trừ phần giao để không đếm trùng những số vừa chia hết 3 vừa chia hết 5).
4
Lấy phần bù trên tổng thể 100 số: số KHÔNG chia hết cho 3 và không chia hết cho 5 là $100-47=53$ . Vậy có $53$ số từ 1 đến 100 thỏa mãn yêu cầu đề bài.
Lấy phần bù trên tổng thể 100 số: số KHÔNG chia hết cho 3 và không chia hết cho 5 là $100-47=53$. Vậy có $53$ số từ 1 đến 100 thỏa mãn yêu cầu đề bài.

Sai lầm thường gặp

Bẫy thường gặp

Khi đếm bù với 2 điều kiện phủ định đồng thời ("không X và không Y"), rất nhiều bạn quên trừ phần GIAO $|A\cap B|$ và tính nhầm $|A\cup B|=|A|+|B|$ , dẫn đến trừ quá tay ở bước lấy phần bù. Luôn vẽ nháp sơ đồ Venn hoặc viết rõ công thức bao hàm - loại trừ trước khi tính. Lỗi thứ hai hay gặp ở bài xếp hàng "không cạnh nhau": quên nhân thêm $2$ cho số cách xếp NỘI BỘ của khối buộc chùm (khối "AB" và "BA" là hai cách xếp khác nhau), khiến kết quả phần đối lập bị tính thiếu đúng một nửa.

Khi đếm bù với 2 điều kiện phủ định đồng thời ("không X và không Y"), rất nhiều bạn quên trừ phần GIAO $|A\cap B|$ và tính nhầm $|A\cup B|=|A|+|B|$, dẫn đến trừ quá tay ở bước lấy phần bù. Luôn vẽ nháp sơ đồ Venn hoặc viết rõ công thức bao hàm - loại trừ trước khi tính. Lỗi thứ hai hay gặp ở bài xếp hàng "không cạnh nhau": quên nhân thêm $2$ cho số cách xếp NỘI BỘ của khối buộc chùm (khối "AB" và "BA" là hai cách xếp khác nhau), khiến kết quả phần đối lập bị tính thiếu đúng một nửa.

Đếm bằng phần bù

Mục tiêu

Khởi động: so sánh với cách làm trực tiếp

Ý tưởng chính: đếm bù

Ví dụ áp dụng

Sai lầm thường gặp

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

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