Kỹ thuật phân tập đồng dư giải bài toán tổ hợp - xác suất có yếu tố chia hết

CHUYÊN ĐỀ: PHÂN TẬP ĐỒNG DƯ

Trung tâm luyện thi 29Edu

Ngày 8 tháng 9 năm 2026

Tóm tắt nội dung

Năm 1801, nhà toán học Carl Friedrich Gauss, khi ấy mới 24 tuổi, đã giới thiệu một kí hiệu mới trong cuốn Disquisitiones Arithmeticae của mình: a ≡b (mod m). Ba dấu gạch nhỏnhưng mởra một chủđềnghiên cứu mới của sốhọc: đồng dư thức. Và ý tưởng đằng sau nó là: khi bài toán chỉquan tâm tới tính chia hết, ta không cần biết chính xác các sốlà bao nhiêu, chỉcần quan tâm xem chúng dư mấy.

Cho một sốnguyên dương m, mặc dù tập sốtựnhiên N khổng lồcó vô hạn phần tửnhưng nếu xét sốdư của chúng khi chi cho sốm thì các sốdư chỉcó thểlà m số: 0, 1, 2, · · · , m −1. Và tập hợp các sốcó cùng sốdư khi chia cho m được gọi là các lớp thặng dư.

• Tập A0 gồm các sốchia m dư 0 (chia hết)

• Tập A1 gồm các sốchia m dư 1

• Tập A2 gồm các sốchia m dư 2

• · · ·

• Tập Am−1 gồm các sốchia m dư m −1

Chuyên đềnày khai thác chính ý tưởng ấy cho các bài toán tổhợp xác suất: thay vì đếm trong tập gốc, ta phân chia tập dữkiện thành các tập con có cùng sốdư, rồi thực hiện đếm xem lấy bao nhiêu phần tửtừmỗi tập con đểthỏa mãn bài toán. Kĩ thuật này ta có thểgọi là phân tập đồng dư.

Chuyên đề: Phân tập đồng dư Trung tâm luyện thi 29Edu

Mục lục

1 Bài toán mởđầu 3

2 Cơ sởlý thuyết 4 2.1 Đồng dư thức và các phép toán . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2 Phân tập đồng dư . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.3 Bổđềcân bằng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.4 Nguyên lí đếm trên các lớp thặng dư . . . . . . . . . . . . . . . . . . . . . . . . 6 2.5 Phương pháp giải . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

3 Các mô hình bài toán điển hình 8 3.1 Mô hình 1: Phân tập và đếm sốphần tửmỗi lớp thặng dư . . . . . . . . . . . . 8 3.2 Mô hình 2: Chọn k phần tửcó tổng chia hết cho m . . . . . . . . . . . . . . . . 8 3.3 Mô hình 3: Hai sốcó tổng (hoặc hiệu) chia hết cho m . . . . . . . . . . . . . . . 9 3.4 Mô hình 4: Lập sốcó các chữsốđôi một khác nhau chia hết cho 3 hoặc 9 . . . . 10 3.5 Mô hình 5: Kết hợp hai điều kiện chia hết . . . . . . . . . . . . . . . . . . . . . 11 3.6 Mô hình 6: Kĩ thuật phần tửtựdo (bổđềcân bằng) . . . . . . . . . . . . . . . 12 3.7 Mô hình 7: Điền sốvào bảng với dữkiện chia hết . . . . . . . . . . . . . . . . . 12

4 Bài tập tựluyện 14

5 Đáp án 18

Đăng ký học toán HSA/SPT/THPT: 0857342713 2

Chuyên đề: Phân tập đồng dư Trung tâm luyện thi 29Edu

1 Bài toán mởđầu

(Đềthi chính thức TNTHPT 2026)

Trong một trò chơi, bạn Bình cần vượt qua một thửthách. Theo yêu cầu của thửthách, Bình cần điền tất cả15 sốthuộc tập hợp

{0; 1; 2; 3; 4; 5; 6; 7; 8; 10; 11; 12; 15; 16; 20}

vào 15 ô vuông trong hình dưới thỏa mãn đồng thời ba điều kiện sau:

– Mỗi ô điền đúng một sốvà mỗi sốchỉđược sửdụng một lần;

– Hiệu hai sốởhai ô bất kì khác nhau trên cùng một hàng không chia hết cho 5;

– Hiệu hai sốởhai ô bất kì khác nhau trên cùng một cột không chia hết cho 5. Hai cách điền gọi là giống nhau nếu sốđiền ởmỗi ô tương ứng trong 15 ô là giống nhau (không tính đến thứtựđiền các sốvào 15 ô vuông). Gọi H là sốcách điền khác nhau đểbạn Bình

vượt qua được thửthách. Giá trịcủa H

30 bằng bao nhiêu?

Hàng 1

Hàng 2

Hàng 3

Hàng 4

Hàng 5

Cột 1Cột 2Cột 3Cột 4Cột 5

Trước hết hãy thấy rõ quy mô của bài toán: chỉriêng việc xếp 15 sốvào 15 ô đã có

15! = 1 307 674 368 000 ≈1,3 · 1012 cách.

Tất nhiên đấy là đếm không có điều kiện gì, và với điều kiện của đềbài "hiệu hai sốtrên một hàng/một cột không chia hết cho 5"thì ta có thểnghĩ đến tính chất "đồng dư":

a −b không chia hết cho 5 ⇐⇒a ̸≡b (mod 5) ⇐⇒a và b khác sốdư khi chia cho 5.

Vậy đềbài đang yêu cầu: các sốtrên cùng một hàng phải đôi một khác sốdư, các số trên cùng một cột cũng vậy. Xếp 15 sốđã cho theo sốdư khi chia cho 5, ta được năm nhóm với sốlượng rất đặc biệt:

Sốdư Các sốtrong tập hợp Sốlượng 0 0; 5; 10; 15; 20 5 1 1; 6; 11; 16 4 2 2; 7; 12 3 3 3; 8 2 4 4 1

Năm nhóm có …