Đây là bản xem thử. Phiên bản đầy đủ trong ứng dụng có bài tập, AI chấm ngay và theo dõi tiến độ học.
Bài học
Đếm bằng chia trường hợp
Mục tiêu
Sau bài học này, em giải được các bài toán đếm phức tạp bằng cách chia thành các trường hợp rời nhau (không giao nhau, không bỏ sót), đếm từng trường hợp rồi cộng lại theo quy tắc cộng.
Kiến thức cần có trước
Em cần nắm vững quy tắc cộng, quy tắc nhân (đã học từ lớp 6-7) và công thức tổ hợp $C_n^k$, chỉnh hợp $A_n^k$ cơ bản. **Mở rộng dành cho HSG**: chương trình chuẩn Lớp 9 (CT GDPT 2018) chưa dạy chính thức tổ hợp-chỉnh hợp (nội dung này ở SGK lớp 10 mới), nhưng đề HSG Lớp 9 cấp tỉnh/thành phố vẫn thường dựa vào các bài đếm cơ bản như một phần mở rộng. Bài học giới thiệu lại công thức $C_n^k = \dfrac{n!}{k!(n-k)!}$ và $A_n^k=\dfrac{n!}{(n-k)!}$ ngay khi cần dùng, không giả định em đã học sẵn.
Khởi động
Câu hỏi mở đầu
Muốn đếm số tự nhiên có 3 chữ số khác nhau chia hết cho 5, em có thể liệt kê từng số một không? Với hàng trăm số như vậy, liệt kê là không khả thi -- ta cần một cách đếm có hệ thống hơn.
Ý tưởng chính: chia trường hợp
Đề thi vào lớp 10 thường chỉ hỏi kiểu "có bao nhiêu số có 2 chữ số chia hết cho 5" -- một điều kiện đơn giản, tính thẳng bằng một công thức là xong. Bài toán HSG thì khác: nó thường trói **hai điều kiện ràng buộc lẫn nhau** vào một bài (ở đây là 3 chữ số khác nhau VÀ chia hết cho 5), nên một công thức chung không còn dùng được nữa. Gặp tình huống đó, tín hiệu để nhận ra là phải **chia trường hợp**: tìm một dấu hiệu cố định (thường là chữ số cuối, tính chẵn lẻ, hoặc số dư khi chia cho một số) để tách bài toán thành từng phần nhỏ, tính riêng từng phần rồi cộng lại.
Nhưng chia thế nào cũng phải chia cho đúng. Hai nguyên tắc bắt buộc: các trường hợp phải *rời nhau đôi một* (không đối tượng nào rơi vào 2 trường hợp, nếu không sẽ đếm trùng), và phải *phủ hết* mọi khả năng (bỏ sót một khả năng là đếm thiếu ngay).
Ví dụ áp dụng
Ví dụ
Số có 3 chữ số khác nhau chia hết cho 5
1
Đếm các số tự nhiên dạng $\overline{abc}$ ($a\neq 0$, $a,b,c$ đôi một khác nhau) chia hết cho 5. Điều kiện chia hết cho 5 chỉ phụ thuộc chữ số hàng đơn vị $c$: $c\in\{0;5\}$. Đây là dấu hiệu tách trường hợp tự nhiên, vì hai giá trị của $c$ dẫn đến số lượng cách chọn $a$ khác nhau (khi $c=0$, $a$ không bị loại giá trị nào trong $\{1,...,9\}$; khi $c=5$, $a$ bị loại thêm giá trị 5).
2
$a$ được chọn từ $\{1,2,...,9\}$ (khác 0, khác $c$): có 9 cách. $b$ được chọn từ 8 chữ số còn lại (10 chữ số trừ $a$ và $c=0$ đã dùng): có 8 cách. Theo quy tắc nhân: $9\times 8=72$ số. (1)
3
$a$ được chọn từ $\{1,...,9\}\setminus\{5\}$: còn 8 cách. $b$ được chọn từ 8 chữ số còn lại (10 chữ số trừ $a$ và $c=5$): có 8 cách. Theo quy tắc nhân: $8\times 8=64$ số. (2)
4
Ta có hai trường hợp $c=0$ và $c=5$ rời nhau (một số không thể vừa có $c=0$ vừa có $c=5$) và phủ hết mọi khả năng chia hết cho 5. Kết hợp (1) và (2) theo quy tắc cộng: $72+64=136$ số. Vậy có tất cả $136$ số tự nhiên có 3 chữ số khác nhau chia hết cho 5.
Chia $\{1,...,20\}$ thành 3 lớp theo số dư mod 3: 6 số dư 0, 7 số dư 1, 7 số dư 2 -- tổng 20 số.
Ví dụ
Chọn đội cầu lông có điều kiện loại trừ (chia trường hợp theo một đối tượng đặc biệt)
1
Một đội cầu lông đôi nam-nữ cần chọn 2 nam từ 5 nam và 2 nữ từ 4 nữ. Riêng bạn X (nam) và Y (nữ) là anh em, quy định không được cùng ở trong đội. Hỏi có bao nhiêu cách chọn? Dấu hiệu chia trường hợp tự nhiên: X có được chọn hay không, vì điều đó quyết định Y có bị cấm hay không.
2
Chọn 2 nam từ 4 nam còn lại (không tính X): $C_4^2=6$ cách. Vì X vắng mặt nên Y không bị ràng buộc: chọn 2 nữ từ 4: $C_4^2=6$ cách. Số cách trong trường hợp này: $6\times 6=36$. (1)
3
X đã chiếm 1 suất nam, chọn thêm 1 nam từ 4 nam còn lại: $C_4^1=4$ cách. Vì Y bị cấm, chọn 2 nữ từ 3 nữ còn lại (không tính Y): $C_3^2=3$ cách. Số cách: $4\times 3=12$. (2)
4
Kết hợp (1) và (2) theo quy tắc cộng: $36+12=48$. Mặt khác, kiểm tra chéo bằng cách khác (đếm bù, sẽ học ở bài sau): tổng không điều kiện là $C_5^2\times C_4^2=10\times 6=60$; số cách cả X và Y cùng được chọn là $C_4^1\times C_3^1=4\times 3=12$ (chọn thêm 1 nam từ 4, 1 nữ từ 3); do đó số cách hợp lệ là $60-12=48$ -- khớp với kết quả trên. Vậy có $48$ cách chọn đội thỏa mãn điều kiện đề bài.
Ví dụ
Kết hợp với số học: đếm theo lớp dư (Mở rộng dành cho HSG)
1
Từ tập $A=\{1,2,...,20\}$, chọn ra 2 số có tổng chia hết cho 3. Hỏi có bao nhiêu cách chọn? Đây là bài toán đếm kết hợp với tính chất số học -- không thể liệt kê 2 số một cách trực tiếp, mà phải chia $A$ theo lớp dư mod 3.
Tổng 2 số chia hết cho 3 khi: cả 2 số cùng dư 0 (vì $0+0\equiv 0$), HOẶC một số dư 1 và một số dư 2 (vì $1+2=3\equiv 0$). Tổng 2 số cùng dư 1 cho tổng dư 2 (không nhận); cùng dư 2 cho tổng dư 1 (không nhận) -- đây là lý do ta phải xét CẢ HAI khả năng trên, rời nhau, không còn khả năng thứ ba.
4
Ta có: cả 2 số cùng dư 0 cho $C_6^2=15$ cách chọn. (1) Mặt khác, một số dư 1 và một số dư 2 cho $7\times 7=49$ cách (quy tắc nhân, vì đây là 2 tập rời nhau, mỗi cặp là một lựa chọn độc lập). (2) Kết hợp (1) và (2) theo quy tắc cộng: $15+49=64$ cách. Vậy có $64$ cách chọn 2 số trong $A$ có tổng chia hết cho 3.
Sai lầm thường gặp
Bẫy thường gặp
Lỗi phổ biến nhất là chia trường hợp **không rời nhau** (một đối tượng rơi vào 2 trường hợp, dẫn đến đếm trùng), hoặc **bỏ sót một trường hợp** (thường xảy ra khi quên xét cả chữ số 0 là một lựa chọn hợp lệ cho hàng đơn vị/hàng chục nhưng không hợp lệ cho hàng cao nhất). Trước khi cộng các trường hợp, luôn tự hỏi: "Hai trường hợp này có thể xảy ra đồng thời với cùng một đối tượng không?" Nếu có, phải trừ phần giao (nguyên lý bao hàm - loại trừ, sẽ gặp lại ở bài Đếm bằng phần bù).
Luyện tập có hướng dẫn
Luyện tập độc lập
Em cần nắm vững quy tắc cộng, quy tắc nhân (đã học từ lớp 6-7) và công thức tổ hợp Cnk, chỉnh hợp Ank cơ bản. Mở rộng dành cho HSG: chương trình chuẩn Lớp 9 (CT GDPT 2018) chưa dạy chính thức tổ hợp-chỉnh hợp (nội dung này ở SGK lớp 10 mới), nhưng đề HSG Lớp 9 cấp tỉnh/thành phố vẫn thường dựa vào các bài đếm cơ bản như một phần mở rộng. Bài học giới thiệu lại công thức Cnk=k!(n−k)!n! và Ank=(n−k)!n! ngay khi cần dùng, không giả định em đã học sẵn.
Đề thi vào lớp 10 thường chỉ hỏi kiểu "có bao nhiêu số có 2 chữ số chia hết cho 5" -- một điều kiện đơn giản, tính thẳng bằng một công thức là xong. Bài toán HSG thì khác: nó thường trói hai điều kiện ràng buộc lẫn nhau vào một bài (ở đây là 3 chữ số khác nhau VÀ chia hết cho 5), nên một công thức chung không còn dùng được nữa. Gặp tình huống đó, tín hiệu để nhận ra là phải chia trường hợp: tìm một dấu hiệu cố định (thường là chữ số cuối, tính chẵn lẻ, hoặc số dư khi chia cho một số) để tách bài toán thành từng phần nhỏ, tính riêng từng phần rồi cộng lại.
Nhưng chia thế nào cũng phải chia cho đúng. Hai nguyên tắc bắt buộc: các trường hợp phải rời nhau đôi một (không đối tượng nào rơi vào 2 trường hợp, nếu không sẽ đếm trùng), và phải phủ hết mọi khả năng (bỏ sót một khả năng là đếm thiếu ngay).
Đếm các số tự nhiên dạng abc (a=0, a,b,c đôi một khác nhau) chia hết cho 5. Điều kiện chia hết cho 5 chỉ phụ thuộc chữ số hàng đơn vị c: c∈{0;5}. Đây là dấu hiệu tách trường hợp tự nhiên, vì hai giá trị của c dẫn đến số lượng cách chọn a khác nhau (khi c=0, a không bị loại giá trị nào trong {1,...,9}; khi c=5, a bị loại thêm giá trị 5).
a được chọn từ {1,2,...,9} (khác 0, khác c): có 9 cách. b được chọn từ 8 chữ số còn lại (10 chữ số trừ a và c=0 đã dùng): có 8 cách. Theo quy tắc nhân: 9×8=72 số. (1)
a được chọn từ {1,...,9}∖{5}: còn 8 cách. b được chọn từ 8 chữ số còn lại (10 chữ số trừ a và c=5): có 8 cách. Theo quy tắc nhân: 8×8=64 số. (2)
Ta có hai trường hợp c=0 và c=5 rời nhau (một số không thể vừa có c=0 vừa có c=5) và phủ hết mọi khả năng chia hết cho 5. Kết hợp (1) và (2) theo quy tắc cộng: 72+64=136 số. Vậy có tất cả 136 số tự nhiên có 3 chữ số khác nhau chia hết cho 5.
Chia {1,...,20} thành 3 lớp theo số dư mod 3: 6 số dư 0, 7 số dư 1, 7 số dư 2 -- tổng 20 số.
Chọn 2 nam từ 4 nam còn lại (không tính X): C42=6 cách. Vì X vắng mặt nên Y không bị ràng buộc: chọn 2 nữ từ 4: C42=6 cách. Số cách trong trường hợp này: 6×6=36. (1)
X đã chiếm 1 suất nam, chọn thêm 1 nam từ 4 nam còn lại: C41=4 cách. Vì Y bị cấm, chọn 2 nữ từ 3 nữ còn lại (không tính Y): C32=3 cách. Số cách: 4×3=12. (2)
Kết hợp (1) và (2) theo quy tắc cộng: 36+12=48. Mặt khác, kiểm tra chéo bằng cách khác (đếm bù, sẽ học ở bài sau): tổng không điều kiện là C52×C42=10×6=60; số cách cả X và Y cùng được chọn là C41×C31=4×3=12 (chọn thêm 1 nam từ 4, 1 nữ từ 3); do đó số cách hợp lệ là 60−12=48 -- khớp với kết quả trên. Vậy có 48 cách chọn đội thỏa mãn điều kiện đề bài.
Từ tập A={1,2,...,20}, chọn ra 2 số có tổng chia hết cho 3. Hỏi có bao nhiêu cách chọn? Đây là bài toán đếm kết hợp với tính chất số học -- không thể liệt kê 2 số một cách trực tiếp, mà phải chia A theo lớp dư mod 3.
Tổng 2 số chia hết cho 3 khi: cả 2 số cùng dư 0 (vì 0+0≡0), HOẶC một số dư 1 và một số dư 2 (vì 1+2=3≡0). Tổng 2 số cùng dư 1 cho tổng dư 2 (không nhận); cùng dư 2 cho tổng dư 1 (không nhận) -- đây là lý do ta phải xét CẢ HAI khả năng trên, rời nhau, không còn khả năng thứ ba.
Ta có: cả 2 số cùng dư 0 cho C62=15 cách chọn. (1) Mặt khác, một số dư 1 và một số dư 2 cho 7×7=49 cách (quy tắc nhân, vì đây là 2 tập rời nhau, mỗi cặp là một lựa chọn độc lập). (2) Kết hợp (1) và (2) theo quy tắc cộng: 15+49=64 cách. Vậy có 64 cách chọn 2 số trong A có tổng chia hết cho 3.
Lỗi phổ biến nhất là chia trường hợp không rời nhau (một đối tượng rơi vào 2 trường hợp, dẫn đến đếm trùng), hoặc bỏ sót một trường hợp (thường xảy ra khi quên xét cả chữ số 0 là một lựa chọn hợp lệ cho hàng đơn vị/hàng chục nhưng không hợp lệ cho hàng cao nhất). Trước khi cộng các trường hợp, luôn tự hỏi: "Hai trường hợp này có thể xảy ra đồng thời với cùng một đối tượng không?" Nếu có, phải trừ phần giao (nguyên lý bao hàm - loại trừ, sẽ gặp lại ở bài Đếm bằng phần bù).