Nguyên lý Dirichlet

Mức độ: Cơ bản

Nguyên lý Dirichlet (còn gọi là nguyên lý chuồng bồ câu) nghe rất hiển nhiên, nhưng lại giải được những bài “chắc chắn”, “ít nhất bao nhiêu” xuất hiện thường xuyên trong đề Tin học trẻ và học sinh giỏi. Trong lập trình, nó giải thích vì sao mọi dãy số dư đều lặp lại.

Phát biểu

Nhốt 5 con chim vào 4 chuồng thì chắc chắn có một chuồng chứa ít nhất 2 con. Vì nếu chuồng nào cũng chỉ có tối đa 1 con thì 4 chuồng chứa tối đa 4 con, không đủ 5.

Dạng tổng quát: nhốt n con chim vào k chuồng thì có chuồng chứa ít nhất ⌈n / k⌉ con (⌈ ⌉ là làm tròn lên). Ví dụ lớp 40 bạn thì có ít nhất ⌈40 / 12⌉ = 4 bạn sinh cùng tháng.

Trong code, ⌈n / k⌉ viết là (n + k - 1) // k (bài số xe ít nhất).

Bài toán trường hợp xấu nhất

Ngăn kéo tối có tất 5 màu, mỗi màu rất nhiều. Lấy ít nhất bao nhiêu chiếc để chắc chắn có 2 chiếc cùng màu?

Cách nghĩ: tưởng tượng một người cố tình lấy giúp mình theo cách tệ nhất. Người đó lấy mỗi màu 1 chiếc, được 5 chiếc mà chưa có đôi nào. Chiếc thứ 6 dù màu gì cũng trùng một màu đã có. Đáp số 6.

Quy tắc chung: đáp số = số lượng lớn nhất có thể lấy mà vẫn chưa đạt yêu cầu, cộng 1.

Ví dụ có số lượng giới hạn: hộp có 6 bi đỏ, 5 bi xanh, 4 bi vàng. Lấy ít nhất bao nhiêu viên để chắc chắn có 3 viên cùng màu? Trường hợp xấu nhất: lấy 2 đỏ, 2 xanh, 2 vàng, 6 viên vẫn chưa có 3 viên cùng màu. Viên thứ 7 chắc chắn tạo thành 3 viên cùng màu. Đáp số 7.

Nếu đòi có đủ cả 3 màu: trường hợp xấu nhất là lấy hết hai màu nhiều nhất (6 đỏ + 5 xanh = 11 viên) mà chưa có vàng. Đáp số 12.

Lưu ý: “chắc chắn” nghĩa là đúng trong mọi trường hợp, nên phải tính theo trường hợp xấu nhất. Nếu chỉ “có thể có” thì lấy 3 viên đã đủ (nếu may mắn).

Dirichlet trong lập trình: số dư luôn lặp lại

Xét dãy x_{i + 1} = (3 × x_i + 4) % 100 bắt đầu từ x₀ = 1. Mỗi số trong dãy chỉ có 100 giá trị có thể (0 đến 99). Theo Dirichlet, trong 101 số đầu tiên chắc chắn có hai số bằng nhau, và từ đó dãy lặp lại mãi. Đây là lý do:

• Chữ số tận cùng của 7ⁿ lặp theo chu kỳ (bài chữ số tận cùng của lũy thừa).
• Dãy Fibonacci chia lấy dư cho m cũng lặp lại (bài 19).

Đoạn con có tổng chia hết cho n: với dãy n số bất kỳ, xét n + 1 tổng tiền tố P₀ = 0, P₁, …, P_n. Chúng chỉ có n số dư khi chia cho n, nên có hai tổng tiền tố cùng số dư, và đoạn giữa chúng có tổng chia hết cho n. Nghĩa là luôn tồn tại một đoạn như vậy, và chỉ cần duyệt một lần để tìm (bài 16).

Python

n = int(input())
a = list(map(int, input().split()))
gap_lan_dau = {0: 0}          # số dư -> vị trí tổng tiền tố đầu tiên có số dư đó
p = 0
for j in range(1, n + 1):
    p = (p + a[j - 1]) % n
    if p in gap_lan_dau:
        print(gap_lan_dau[p] + 1, j)   # đoạn từ vị trí gap_lan_dau[p] + 1 đến j
        break
    gap_lan_dau[p] = j

C++

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> a(n);
    for (auto& x : a) cin >> x;
    vector<int> gapLanDau(n, -1);   // số dư -> vị trí tổng tiền tố đầu tiên
    gapLanDau[0] = 0;
    long long p = 0;
    for (int j = 1; j <= n; j++) {
        p = (p + a[j - 1]) % n;
        if (gapLanDau[p] != -1) {
            cout << gapLanDau[p] + 1 << " " << j << endl;
            break;
        }
        gapLanDau[p] = j;
    }
    return 0;
}

Số lần cân ít nhất

Có n đồng xu, đúng một đồng giả nhẹ hơn, dùng cân hai đĩa. Mỗi lần cân có 3 kết quả: lệch trái, lệch phải, cân bằng. Sau k lần cân có tối đa 3^k “dãy kết quả” khác nhau. Nếu 3^k nhỏ hơn n thì theo Dirichlet có hai đồng xu cho cùng dãy kết quả, không phân biệt được. Vậy cần ít nhất k lần với 3^k ≥ n, và chia 3 nhóm mỗi lần thì đạt đúng số lần đó.

Với 9 đồng: chia 3 nhóm 3 đồng, cân hai nhóm để biết nhóm chứa đồng giả, rồi lặp lại với 3 đồng: 2 lần.

Luyện tập

Gồm 20 bài, chia thành 3 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. Trường hợp xấu nhất

Bài 1. Lấy tất cùng màu

Ngăn kéo tối có tất k màu, mỗi màu rất nhiều chiếc (k ≤ 10⁹). Lấy ít nhất bao nhiêu chiếc để chắc chắn có 2 chiếc cùng màu?

Ví dụ: nhập 3 thì in ra 4.

Kiểm tra: nhập 5.

Xem đáp số

6

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 2. Chắc chắn có m chiếc cùng màu

Ngăn kéo có tất k màu, mỗi màu rất nhiều chiếc (k, m ≤ 10⁹). Lấy ít nhất bao nhiêu chiếc để chắc chắn có m chiếc cùng màu?

Ví dụ: nhập 3 2 thì in ra 4.

Kiểm tra: nhập 4 5.

Xem đáp số

17

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 3. Bi màu có số lượng giới hạn

Dòng đầu có k và m (k ≤ 10⁵, m ≤ 10⁹). Dòng thứ hai có k số c₁, …, c_k: số bi của từng màu. Lấy ít nhất bao nhiêu viên để chắc chắn có m viên cùng màu? Nếu không thể (không màu nào có đủ m viên) thì in ra -1.

Ví dụ:

Nhập	In ra
3 2 1 1 5	4

Kiểm tra: nhập

3 3
6 5 4

Xem đáp số

7

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 4. Chắc chắn có đủ mọi màu

Dòng đầu có k (k ≤ 10⁵). Dòng thứ hai có k số c_i ≥ 1: số bi của từng màu. Lấy ít nhất bao nhiêu viên để chắc chắn có đủ cả k màu?

Ví dụ:

Nhập	In ra
2 3 5	6

Kiểm tra: nhập

3
6 5 4

Xem đáp số

12

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 5. Chắc chắn có hai viên màu đỏ

Hộp có a bi đỏ (a ≥ 2) và b bi màu khác (a, b ≤ 10⁹). Lấy ít nhất bao nhiêu viên để chắc chắn có ít nhất 2 viên đỏ?

Ví dụ: nhập 3 4 thì in ra 6.

Kiểm tra: nhập 6 9.

Xem đáp số

11

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 6. Hai viên kẹo khác vị

Hộp tối có a viên kẹo dâu và b viên kẹo cam (a, b ≥ 1, a, b ≤ 10⁹). Lấy ít nhất bao nhiêu viên để chắc chắn có hai viên khác vị?

Ví dụ: nhập 3 5 thì in ra 6.

Kiểm tra: nhập 10 7.

Xem đáp số

11

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 7. Găng tay trái phải

Ngăn kéo tối có k đôi găng tay, mỗi đôi một màu khác nhau, mỗi đôi gồm 1 chiếc tay trái và 1 chiếc tay phải (k ≤ 10⁹). Lấy ít nhất bao nhiêu chiếc để chắc chắn có một đôi dùng được (một chiếc trái và một chiếc phải cùng màu)?

Ví dụ: nhập 1 thì in ra 2.

Kiểm tra: nhập 10.

Xem đáp số

11

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 8. Hai số có tổng bằng n + 1

Có n quả bóng ghi số 1, 2, …, n (n ≤ 10⁹). Lấy ít nhất bao nhiêu quả để chắc chắn có hai quả có tổng hai số bằng n + 1? Nếu không bao giờ chắc chắn được thì in ra -1.

Ví dụ: nhập 6 thì in ra 4.

Kiểm tra: nhập 49.

Xem đáp số

26

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 9. Hai số liên tiếp

Chọn các số khác nhau từ 1 đến n (n ≤ 10⁹). Cần chọn ít nhất bao nhiêu số để chắc chắn có hai số liên tiếp (hơn kém nhau 1)? Nếu không thể thì in ra -1.

Ví dụ: nhập 4 thì in ra 3.

Kiểm tra: nhập 10.

Xem đáp số

6

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 2. Dirichlet tổng quát, cân và đoán số

Bài 10. Hộp nhiều nhất

Bỏ n đồ vật vào k hộp (n, k ≤ 10¹⁸). Hỏi chắc chắn có một hộp chứa ít nhất bao nhiêu đồ vật?

Ví dụ: nhập 10 3 thì in ra 4.

Kiểm tra: nhập 2026 7.

Xem đáp số

290

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 11. Cùng tháng sinh

Lớp có n bạn (n ≤ 10⁹). Chắc chắn có ít nhất bao nhiêu bạn sinh cùng một tháng?

Ví dụ: nhập 13 thì in ra 2.

Kiểm tra: nhập 40.

Xem đáp số

4

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 12. Nhiều học sinh nhất mà không ai trùng quá m

Trường muốn có thể xếp học sinh sao cho không có quá m bạn trùng ngày sinh (năm có 366 ngày kể cả 29/2). Trường có nhiều nhất bao nhiêu học sinh thì điều đó còn có thể xảy ra? Nhập d (số ngày) và m (d, m ≤ 10⁹).

Ví dụ: nhập 366 1 thì in ra 366.

Kiểm tra: nhập 366 3.

Xem đáp số

1098

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 13. Cân tìm đồng xu nhẹ

Có n đồng xu (n ≤ 10¹⁸), đúng một đồng giả nhẹ hơn các đồng còn lại. Dùng cân hai đĩa không có quả cân. Cần ít nhất bao nhiêu lần cân để chắc chắn tìm ra đồng giả?

Ví dụ: nhập 9 thì in ra 2.

Kiểm tra: nhập 2026.

Xem đáp số

7

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 14. Đoán số

Bạn An nghĩ một số từ 1 đến n (n ≤ 10¹⁸). Mỗi lần Bình đoán một số, An trả lời “đúng”, “lớn hơn” hoặc “nhỏ hơn”. Bình cần ít nhất bao nhiêu lần đoán để chắc chắn đoán đúng?

Ví dụ: nhập 7 thì in ra 3.

Kiểm tra: nhập 1000.

Xem đáp số

10

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 15. Chọn số để có một số chia hết cho số kia

Chọn các số khác nhau từ 1 đến 2n (n ≤ 10⁹). Cần chọn ít nhất bao nhiêu số để chắc chắn có hai số mà số này chia hết cho số kia?

Ví dụ: nhập 3 thì in ra 4.

Kiểm tra: nhập 100.

Xem đáp số

101

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 3. Dirichlet trong lập trình

Bài 16. Đoạn có tổng chia hết cho n

Dòng đầu là n (n ≤ 10⁵). Dòng thứ hai có n số nguyên dương (mỗi số ≤ 10⁹). Theo nguyên lý Dirichlet luôn có một đoạn liên tiếp có tổng chia hết cho n. In ra vị trí đầu và cuối (đánh số từ 1) của đoạn kết thúc sớm nhất; nếu nhiều đoạn cùng kết thúc ở đó thì chọn đoạn dài nhất.

Ví dụ:

Nhập	In ra
3 1 1 1	1 3

Kiểm tra: nhập

8
3 1 4 1 5 9 2 6

Xem đáp số

1 3

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 17. Hai số có hiệu chia hết cho n

Dòng đầu là n (n ≤ 10⁵). Dòng thứ hai có n + 1 số nguyên dương. Luôn có hai số có hiệu chia hết cho n. In ra vị trí (đánh số từ 1) của cặp có số thứ hai xuất hiện sớm nhất, số thứ nhất là số đầu tiên cùng số dư với nó.

Ví dụ:

Nhập	In ra
3 1 2 3 4	1 4

Kiểm tra: nhập

6
17 8 29 13 4 30 23

Xem đáp số

1 3

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 18. Trung điểm có tọa độ nguyên

Dòng đầu là k (5 ≤ k ≤ 10⁵). k dòng tiếp theo, mỗi dòng là tọa độ nguyên (x, y) của một điểm. Luôn có hai điểm mà trung điểm của chúng có tọa độ nguyên. In ra vị trí của cặp có điểm thứ hai xuất hiện sớm nhất (điểm thứ nhất là điểm đầu tiên ghép được với nó).

Ví dụ:

Nhập	In ra
5 0 0 1 1 2 3 1 0 2 2	1 5

Kiểm tra: nhập

5
1 2
3 5
4 4
7 1
6 9

Xem đáp số

2 4

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 19. Chu kỳ Fibonacci theo modulo

Dãy Fibonacci chia lấy dư cho m: 0, 1, 1, 2, 3, 5, … (mỗi số bằng tổng hai số trước, lấy dư cho m). Dãy này luôn lặp lại theo chu kỳ. Nhập m (2 ≤ m ≤ 10⁴), in ra độ dài chu kỳ (số bước nhỏ nhất để cặp (0, 1) xuất hiện lại).

Ví dụ: nhập 2 thì in ra 3.

Kiểm tra: nhập 10.

Xem đáp số

60

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 20. Dãy số dư lặp lại

Dãy x₀, x₁, … với x_{i + 1} = (a × x_i + b) % m. Nhập x₀, a, b, m (m ≤ 10⁶, các số không âm và nhỏ hơn m). Dãy chắc chắn lặp lại: in ra vị trí đầu tiên bắt đầu vòng lặp và độ dài vòng lặp.

Ví dụ: nhập 1 2 0 7 thì in ra 0 3.

Kiểm tra: nhập 1 3 4 100.

Xem đáp số

0 20

Hướng dẫn giải chi tiết: liên hệ tác giả.

Lời giải chi tiết các bài luyện tập

Đáp số của từng bài ở ngay dưới đề để các bạn tự kiểm tra. Lời giải chi tiết (phân tích, chạy tay, chương trình Python và C++, lưu ý khi làm bài) có trong bộ tài liệu có phí của chuyên đề.

Thầy cô và các bạn muốn mua bộ tài liệu vui lòng liên hệ tác giả qua Zalo 0972465159 hoặc Facebook.