Quy tắc cộng, quy tắc nhân
“Có bao nhiêu cách…?”, “Có bao nhiêu số…?” là câu hỏi rất hay gặp trong cả đề Tin học trẻ lẫn đề học sinh giỏi. Với số nhỏ, máy tính có thể thử hết mọi khả năng (vét cạn). Nhưng khi số khả năng lên tới hàng tỉ, ta cần đếm bằng phép tính. Hai công cụ đầu tiên là quy tắc cộng và quy tắc nhân.
Quy tắc cộng: chọn một trong các nhóm
Phần tiêu đề “Quy tắc cộng: chọn một trong các nhóm”Căng tin có 3 món mặn và 2 món chay. Chọn một món ăn: có 3 + 2 = 5 cách.
Quy tắc: nếu việc chọn chia thành các nhóm không trùng nhau, mỗi lựa chọn thuộc đúng một nhóm, thì số cách bằng tổng số cách của từng nhóm.
Quy tắc nhân: làm lần lượt nhiều bước
Phần tiêu đề “Quy tắc nhân: làm lần lượt nhiều bước”Thỏ có 3 áo (đỏ, xanh, vàng) và 2 quần (đen, trắng). Mặc một bộ gồm 1 áo và 1 quần:
| quần đen | quần trắng | |
|---|---|---|
| áo đỏ | đỏ - đen | đỏ - trắng |
| áo xanh | xanh - đen | xanh - trắng |
| áo vàng | vàng - đen | vàng - trắng |
Mỗi áo đi với 2 quần, có 3 áo, nên có 3 × 2 = 6 bộ.
Quy tắc: nếu công việc gồm nhiều bước liên tiếp, bước 1 có a cách, với mỗi cách đó bước 2 có b cách, …, thì số cách làm cả công việc là a × b × …
Nhận biết nhanh: chữ “hoặc” (chọn một trong các nhóm) thường dùng quy tắc cộng; chữ “và”, “lần lượt” (làm đủ các bước) thường dùng quy tắc nhân.
Kết hợp hai quy tắc
Phần tiêu đề “Kết hợp hai quy tắc”Từ nhà đến trường có 3 đường đi qua nhà sách và mỗi đường từ nhà sách đến trường có 4 lối, ngoài ra còn 2 đường đi thẳng không qua nhà sách:
- Đi qua nhà sách: 3 × 4 = 12 cách (quy tắc nhân).
- Đi thẳng: 2 cách.
- Tổng: 12 + 2 = 14 cách (quy tắc cộng).
Lập số: cẩn thận với chữ số 0
Phần tiêu đề “Lập số: cẩn thận với chữ số 0”Có bao nhiêu số có 3 chữ số khác nhau? Chọn lần lượt từng chữ số, bắt đầu từ chữ số có điều kiện khó nhất:
| Bước | Điều kiện | Số cách |
|---|---|---|
| Chữ số hàng trăm | khác 0 | 9 |
| Chữ số hàng chục | khác chữ số hàng trăm (được là 0) | 9 |
| Chữ số hàng đơn vị | khác hai chữ số trên | 8 |
Đáp số 9 × 9 × 8 = 648.
Lưu ý: chọn chữ số hàng trăm trước vì nó có điều kiện riêng (khác 0). Nếu chọn hàng đơn vị trước, số cách của hàng trăm sẽ phụ thuộc vào việc hàng đơn vị có phải là 0 hay không, và không nhân thẳng được nữa. Khi gặp tình huống như vậy, chia thành các trường hợp rồi cộng lại (bài 7).
Đếm phần bù
Phần tiêu đề “Đếm phần bù”“Có bao nhiêu số có 4 chữ số chứa ít nhất một chữ số 0?” Đếm trực tiếp rất rối (một số 0, hai số 0, ở vị trí nào…). Đếm phần còn lại thì dễ:
- Mọi số có 4 chữ số: 9 × 10 × 10 × 10 = 9000.
- Số có 4 chữ số không có chữ số 0 nào: 9 × 9 × 9 × 9 = 6561.
- Đáp số: 9000 - 6561 = 2439.
Kiểm tra bằng vét cạn
Phần tiêu đề “Kiểm tra bằng vét cạn”Khi n nhỏ, viết thêm chương trình thử hết mọi khả năng là cách tự kiểm tra công thức rất tốt. Ví dụ đếm số có 3 chữ số khác nhau:
dem = 0for x in range(100, 1000): s = str(x) if s[0] != s[1] and s[0] != s[2] and s[1] != s[2]: dem += 1print(dem, 9 * 9 * 8) # 648 648#include <iostream>using namespace std;
int main() { int dem = 0; for (int x = 100; x <= 999; x++) { int a = x / 100, b = x / 10 % 10, c = x % 10; if (a != b && a != c && b != c) dem++; } cout << dem << " " << 9 * 9 * 8 << endl; // 648 648 return 0;}Vét cạn chỉ dùng được khi số khả năng nhỏ (khoảng dưới 108). Công thức thì dùng được với mọi n, ví dụ số có 10 chữ số khác nhau: 9 × 9 × 8 × 7 × … × 1 = 3265920, tính ngay mà không cần duyệt 9 × 109 số.
Luyện tập
Phần tiêu đề “Luyện tập”Gồm 23 bài, chia thành 5 nhóm từ dễ đến khó. Mỗi bài có một dữ liệu kiểm tra: các bạn chạy chương trình của mình với dữ liệu đó rồi so với đáp số.
Nhóm 1. Quy tắc cộng và quy tắc nhân
Phần tiêu đề “Nhóm 1. Quy tắc cộng và quy tắc nhân”Bài 1. Chọn trang phục
Phần tiêu đề “Bài 1. Chọn trang phục”Bạn Thỏ có a chiếc áo, b chiếc quần và c đôi giày (a, b, c ≤ 106). Mỗi lần đi chơi, Thỏ chọn 1 áo, 1 quần và 1 đôi giày. Có bao nhiêu cách chọn?
Ví dụ: nhập 3 2 1 thì in ra 6.
Kiểm tra: nhập 5 4 3.
Bài 2. Chọn suất ăn
Phần tiêu đề “Bài 2. Chọn suất ăn”Căng tin có a món mặn, b món chay và c loại đồ uống (a, b, c ≤ 106). Mỗi suất ăn gồm một món (mặn hoặc chay) và một đồ uống. Có bao nhiêu cách chọn suất ăn?
Ví dụ: nhập 3 2 4 thì in ra 20.
Kiểm tra: nhập 12 7 9.
Bài 3. Đường đến trường
Phần tiêu đề “Bài 3. Đường đến trường”Từ nhà đến nhà sách có a con đường, từ nhà sách đến trường có b con đường, ngoài ra từ nhà đến thẳng trường có c con đường không qua nhà sách (a, b, c ≤ 106). Có bao nhiêu cách đi từ nhà đến trường?
Ví dụ: nhập 3 4 2 thì in ra 14.
Kiểm tra: nhập 15 12 7.
Bài 4. Mật khẩu số
Phần tiêu đề “Bài 4. Mật khẩu số”Mật khẩu gồm n chữ số (mỗi chữ số từ 0 đến 9, được lặp lại, n ≤ 18). Có bao nhiêu mật khẩu khác nhau?
Ví dụ: nhập 2 thì in ra 100.
Kiểm tra: nhập 6.
Bài 5. Biển số xe
Phần tiêu đề “Bài 5. Biển số xe”Biển số xe gồm a chữ cái rồi b chữ số. Chữ cái lấy từ 26 chữ cái tiếng Anh nhưng không dùng chữ O và chữ I (dễ nhầm với 0 và 1); chữ số từ 0 đến 9. Nhập a, b (a + b ≤ 12), in ra số biển số khác nhau.
Ví dụ: nhập 1 2 thì in ra 2400.
Kiểm tra: nhập 2 4.
Nhóm 2. Lập số
Phần tiêu đề “Nhóm 2. Lập số”Bài 6. Số có các chữ số khác nhau
Phần tiêu đề “Bài 6. Số có các chữ số khác nhau”Nhập n (1 ≤ n ≤ 10). Có bao nhiêu số tự nhiên có đúng n chữ số mà các chữ số đôi một khác nhau?
Ví dụ: nhập 2 thì in ra 81.
Kiểm tra: nhập 3.
Bài 7. Số chẵn có các chữ số khác nhau
Phần tiêu đề “Bài 7. Số chẵn có các chữ số khác nhau”Nhập n (2 ≤ n ≤ 10). Có bao nhiêu số chẵn có đúng n chữ số mà các chữ số đôi một khác nhau?
Ví dụ: nhập 2 thì in ra 41.
Kiểm tra: nhập 3.
Bài 8. Đếm số đối xứng
Phần tiêu đề “Bài 8. Đếm số đối xứng”Nhập n (1 ≤ n ≤ 18). Có bao nhiêu số đối xứng (đọc xuôi ngược như nhau, ví dụ 12321) có đúng n chữ số?
Ví dụ: nhập 3 thì in ra 90.
Kiểm tra: nhập 5.
Bài 9. Xâu từ k chữ cái
Phần tiêu đề “Bài 9. Xâu từ k chữ cái”Có bao nhiêu xâu độ dài n tạo từ k chữ cái cho trước (mỗi chữ dùng được nhiều lần)? Nhập n, k (kn ≤ 1018).
Ví dụ: nhập 2 3 thì in ra 9.
Kiểm tra: nhập 5 4.
Bài 10. Có ít nhất một chữ số 0
Phần tiêu đề “Bài 10. Có ít nhất một chữ số 0”Nhập n (1 ≤ n ≤ 18). Có bao nhiêu số có đúng n chữ số chứa ít nhất một chữ số 0?
Ví dụ: nhập 2 thì in ra 9.
Kiểm tra: nhập 4.
Bài 11. Đếm số chứa chữ số 7
Phần tiêu đề “Bài 11. Đếm số chứa chữ số 7”Nhập n (n ≤ 106). Đếm các số từ 1 đến n có chứa ít nhất một chữ số 7.
Ví dụ: nhập 100 thì in ra 19.
Kiểm tra: nhập 1000.
Nhóm 3. Xếp hàng và phần bù
Phần tiêu đề “Nhóm 3. Xếp hàng và phần bù”Bài 12. Xếp hàng
Phần tiêu đề “Bài 12. Xếp hàng”Có bao nhiêu cách xếp n bạn (n ≤ 20) thành một hàng dọc?
Ví dụ: nhập 3 thì in ra 6.
Kiểm tra: nhập 10.
Bài 13. Hai bạn đứng cạnh nhau
Phần tiêu đề “Bài 13. Hai bạn đứng cạnh nhau”Có n bạn (2 ≤ n ≤ 20) xếp thành một hàng, trong đó có An và Bình. Có bao nhiêu cách xếp sao cho An và Bình đứng cạnh nhau?
Ví dụ: nhập 3 thì in ra 4.
Kiểm tra: nhập 6.
Bài 14. Hai bạn không đứng cạnh nhau
Phần tiêu đề “Bài 14. Hai bạn không đứng cạnh nhau”Có n bạn (2 ≤ n ≤ 20) xếp thành một hàng, trong đó có An và Bình. Có bao nhiêu cách xếp sao cho An và Bình không đứng cạnh nhau?
Ví dụ: nhập 3 thì in ra 2.
Kiểm tra: nhập 6.
Bài 15. Bóng đèn ba trạng thái
Phần tiêu đề “Bài 15. Bóng đèn ba trạng thái”Có n bóng đèn (n ≤ 30), mỗi bóng có ba trạng thái: tắt, sáng xanh, sáng đỏ. Có bao nhiêu cách đặt trạng thái cho các bóng sao cho có ít nhất một bóng sáng?
Ví dụ: nhập 2 thì in ra 8.
Kiểm tra: nhập 5.
Nhóm 4. Tô màu và cặp số
Phần tiêu đề “Nhóm 4. Tô màu và cặp số”Bài 16. Lá cờ ba sọc
Phần tiêu đề “Bài 16. Lá cờ ba sọc”Lá cờ có 3 sọc ngang. Có k màu (k ≤ 106), tô mỗi sọc một màu sao cho hai sọc kề nhau khác màu (sọc trên và sọc dưới được cùng màu). Có bao nhiêu cách tô?
Ví dụ: nhập 2 thì in ra 2.
Kiểm tra: nhập 5.
Bài 17. Tô màu bảng hai hàng
Phần tiêu đề “Bài 17. Tô màu bảng hai hàng”Bảng có 2 hàng và n cột ô (n ≤ 30). Tô mỗi ô màu đen hoặc trắng sao cho mỗi cột có ít nhất một ô đen. Có bao nhiêu cách tô?
Ví dụ: nhập 1 thì in ra 3.
Kiểm tra: nhập 5.
Bài 18. Cặp có tổng chẵn
Phần tiêu đề “Bài 18. Cặp có tổng chẵn”Nhập n (n ≤ 109). Đếm số cặp có thứ tự (a, b) với 1 ≤ a, b ≤ n và a + b là số chẵn.
Ví dụ: nhập 3 thì in ra 5.
Kiểm tra: nhập 2026.
Bài 19. Đếm ước bằng quy tắc nhân
Phần tiêu đề “Bài 19. Đếm ước bằng quy tắc nhân”Cho n = 2a × 3b × 5c (a, b, c ≤ 60). Nhập a, b, c, in ra số ước của n.
Ví dụ: nhập 3 2 1 thì in ra 24.
Kiểm tra: nhập 10 6 3.
Nhóm 5. Đếm trên hình và lưới
Phần tiêu đề “Nhóm 5. Đếm trên hình và lưới”Bài 20. Bắt tay
Phần tiêu đề “Bài 20. Bắt tay”Trong buổi gặp mặt có n người (n ≤ 109), mỗi hai người bắt tay nhau đúng một lần. Có tất cả bao nhiêu cái bắt tay?
Ví dụ: nhập 4 thì in ra 6.
Kiểm tra: nhập 2026.
Bài 21. Tam giác từ hai đường thẳng
Phần tiêu đề “Bài 21. Tam giác từ hai đường thẳng”Trên đường thẳng d1 có n điểm, trên đường thẳng d2 song song với d1 có m điểm (n, m ≤ 106). Có bao nhiêu tam giác có ba đỉnh là ba trong số các điểm đó?
Ví dụ: nhập 2 2 thì in ra 4.
Kiểm tra: nhập 4 5.
Bài 22. Đếm hình chữ nhật trên lưới
Phần tiêu đề “Bài 22. Đếm hình chữ nhật trên lưới”Lưới ô vuông có m hàng và n cột ô (m, n ≤ 106). Đếm số hình chữ nhật (kể cả hình vuông) có các cạnh nằm trên các đường kẻ của lưới.
Ví dụ: nhập 1 2 thì in ra 3.
Kiểm tra: nhập 3 5.
Bài 23. Đếm hình vuông trên lưới
Phần tiêu đề “Bài 23. Đếm hình vuông trên lưới”Lưới ô vuông có m hàng và n cột ô (m, n ≤ 106). Đếm số hình vuông có các cạnh nằm trên các đường kẻ của lưới.
Ví dụ: nhập 2 2 thì in ra 5.
Kiểm tra: nhập 3 5.
© 2026 Bumbii Academy. Toàn bộ nội dung thuộc bản quyền của Bumbii Academy, nghiêm cấm sao chép dưới mọi hình thức khi chưa được cho phép.