Bài viết tổng hợp lý thuyết nền tảng và phương pháp giải bài toán nâng cao thuộc chuyên đề Tổ hợp – Xác suất với chủ đề Phân tập đồng dư và...
A. LÝ THUYẾT VÀ PHƯƠNG PHÁP GIẢI
1. Chia tập hợp theo số dư
Hai số \(a, b\) đồng dư theo modulo \(m\) khi \(a - b\) chia hết cho \(m\), ký hiệu \(a \equiv b \pmod{m}\).
- Chọn modulo \(m\) theo điều kiện chia hết trong đề.
- Chia tập nguồn thành các lớp \(R_0, R_1, \dots, R_{m-1}\). Lớp \(R_r\) gồm các số chia cho \(m\) dư \(r\).
- Đếm số phần tử từng lớp. Nếu tập nguồn là một đoạn số nguyên liên tiếp và lớp khác rỗng, lấy số cuối trừ số đầu, chia cho \(m\), rồi cộng 1.
Khi xét tổng, hiệu hoặc tích theo modulo \(m\), có thể thay mỗi số bằng số dư tương ứng.
2. Chọn số thỏa điều kiện chia hết
- Tổng chia hết cho \(m\): Liệt kê các kiểu số dư có tổng chia hết cho \(m\). Nếu lấy \(k_r\) phần tử từ lớp \(R_r\) có \(n_r\) phần tử, dùng \(C_{n_r}^{k_r}\) cho lớp đó. Nhân trong từng kiểu, rồi cộng các kiểu rời nhau.
- Hiệu chia hết cho \(m\): Hai số phải thuộc cùng lớp dư.
- Tích chia hết: Xét số dư của tích hoặc lượng thừa số nguyên tố cần có. Ví dụ: tích chia hết cho 4 nếu có một thừa số chia hết cho 4 hoặc có ít nhất hai thừa số chẵn.
Ví dụ nhanh: Chọn 3 số có tổng chia hết cho 3 từ 1 đến 9.
Ba số dư có thể cùng bằng 0, 1, 2 (mỗi giá trị là một trường hợp), hoặc là 0, 1, 2 đôi một khác nhau.
Mỗi lớp có 3 số, nên có \(3C_3^3 + 3^3 = 30\) cách chọn.
3. Lập số tự nhiên
- Xét chữ số cuối: Dùng chữ số cuối cho điều kiện chia hết cho 2, 5 và hai chữ số cuối cho 4, 25.
- Xét tổng chữ số: Với modulo 3 hoặc 9, chọn các chữ số có tổng phù hợp rồi xếp vào các vị trí.
- Xét vị trí xen kẽ: Với modulo 11, hiệu tổng chữ số ở hai nhóm vị trí xen kẽ phải chia hết cho 11.
- Phối hợp điều kiện: Chia hết cho 6 cần chữ số cuối chẵn và tổng chữ số chia hết cho 3. Chia hết cho 15 cần chữ số cuối là 0 hoặc 5 và tổng chữ số chia hết cho 3.
- Kiểm tra chữ số đầu: Nếu có 0, cố định chữ số đầu khác 0 hoặc trừ các cách xếp bắt đầu bằng 0.
4. Điền bảng theo lớp dư
Hiệu hai số không chia hết cho \(m\) khi hai số thuộc hai lớp dư khác nhau. Điền lớp dư trước, sau đó hoán vị các số cụ thể trong từng lớp.
- Với bảng bậc thang có \(h\) hàng và \(h\) cột, nếu một lớp có \(h\) số và mỗi hàng, mỗi cột chứa tối đa một số thuộc lớp đó, lớp này phải xuất hiện đúng một lần trên từng hàng và từng cột.
- Bắt đầu ở hàng chỉ có một ô. Tiếp tục lên các hàng dài hơn và loại các cột đã dùng. Sau khi bỏ các ô đã xác định, xét bảng còn lại.
- Với mỗi mẫu lớp dư hợp lệ, nếu lớp \(R_r\) có \(n_r\) số, có \(n_r!\) cách xếp các số đó vào các ô của lớp.
5. Xác suất
Khi các kết quả đồng khả năng, chia số kết quả thuận lợi cho số kết quả của không gian mẫu.
