Nguyên lý Dirichlet (còn gọi là nguyên lý cái hộp) là một công cụ rất mạnh trong các bài toán tồn tại. Ý tưởng cốt lõi rất đơn giản: nếu số đối tượng nhiều hơn số “ngăn” dùng để phân loại chúng thì ít nhất một ngăn phải chứa nhiều hơn một đối tượng.
Phạm vi: Đây là nội dung Toán THCS nâng cao, phù hợp học sinh khá giỏi, ôn HSG và thi vào lớp 10 chuyên; không phải toàn bộ kiến thức trong bài đều thuộc yêu cầu chính khóa.
1. Phát biểu cơ bản và dạng tổng quát
Nếu phân \(n+1\) đối tượng vào \(n\) ngăn thì tồn tại ít nhất một ngăn chứa từ hai đối tượng trở lên.
Dạng tổng quát hơn: nếu phân \(N\) đối tượng vào \(k\) ngăn thì có ít nhất một ngăn chứa không ít hơn
\(\left\lceil\dfrac{N}{k}\right\rceil\)
đối tượng. Ký hiệu \(\lceil x\rceil\) là số nguyên nhỏ nhất không nhỏ hơn \(x\).
2. Điều khó nhất: chọn đúng “đối tượng” và “ngăn”
Trong bài toán Dirichlet, phép chia thường không khó. Điểm quyết định là mô hình hóa:
- Đối tượng là những phần tử đang được xét: học sinh, số nguyên, điểm, đoạn thẳng, phần tử của một tập hợp…
- Ngăn là các nhóm dùng để phân loại đối tượng: tháng sinh, số dư, các cặp số, khoảng giá trị…
Một cách chọn ngăn tốt phải thỏa hai điều: mọi đối tượng đều rơi vào ít nhất một ngăn và số ngăn đủ ít để tạo ra sự “chật chội”.
3. Ví dụ 1: tháng sinh
Bài toán. Chứng minh trong 13 học sinh luôn có ít nhất hai bạn sinh cùng tháng.
Lời giải. Có 13 học sinh là 13 đối tượng và 12 tháng là 12 ngăn. Vì \(13>12\), theo nguyên lý Dirichlet có ít nhất một tháng chứa từ hai học sinh trở lên. Vậy có ít nhất hai bạn sinh cùng tháng.
4. Ví dụ 2: dùng số dư làm ngăn
Bài toán. Chọn bất kỳ 7 số nguyên. Chứng minh luôn có hai số có hiệu chia hết cho 6.
Lời giải. Khi chia một số nguyên cho 6, số dư chỉ có thể là \(0,1,2,3,4,5\). Ta có 6 lớp số dư, tức 6 ngăn. Chọn 7 số nguyên nên có hai số cùng số dư khi chia cho 6. Gọi chúng là \(a,b\). Khi đó \(a\equiv b\pmod{6}\), suy ra \(a-b\) chia hết cho 6.
Đây là mẫu rất thường gặp: muốn chứng minh hiệu của hai số chia hết cho \(m\), hãy nghĩ tới việc phân loại theo số dư modulo \(m\).
5. Ví dụ 3: ghép cặp để tạo ngăn
Bài toán. Chọn 6 số khác nhau từ tập \(\{1,2,3,\ldots,10\}\). Chứng minh có hai số liên tiếp.
Lời giải. Chia 10 số thành 5 cặp:
\(\{1,2\}\), \(\{3,4\}\), \(\{5,6\}\), \(\{7,8\}\), \(\{9,10\}\).
Sáu số được chọn rơi vào 5 cặp. Theo Dirichlet, có một cặp chứa hai số đã chọn. Hai số trong cùng một cặp hơn kém nhau 1, nên chúng là hai số liên tiếp.
6. Dạng tổng quát “ít nhất bao nhiêu?”
Nếu có 25 học sinh và 12 tháng sinh thì không chỉ kết luận “có hai bạn cùng tháng”. Ta có
\(\left\lceil\dfrac{25}{12}\right\rceil=3,\)
nên tồn tại ít nhất một tháng có từ 3 học sinh trở lên.
Khi đề hỏi số lượng tối thiểu trong một nhóm, nên kiểm tra ngay dạng \(\left\lceil N/k\right\rceil\).
7. Các lỗi thường gặp
- Chọn “ngăn” không bao phủ hết các đối tượng.
- Số ngăn nhiều bằng hoặc nhiều hơn số đối tượng nên không tạo được kết luận cần thiết.
- Kết luận quá mạnh. Dirichlet chỉ đảm bảo tồn tại ít nhất một ngăn đủ đông, không nói mọi ngăn đều như vậy.
- Dùng số dư nhưng quên rằng khi chia cho \(m\) chỉ có đúng \(m\) lớp dư \(0,1,\ldots,m-1\).
8. Bài tập tự luyện
- Trong 25 học sinh, chứng minh có ít nhất 3 bạn sinh cùng tháng.
- Chọn 11 số nguyên bất kỳ. Chứng minh có hai số có hiệu chia hết cho 10.
- Chọn 6 số khác nhau từ \(1\) đến \(10\). Chứng minh có hai số liên tiếp.
- Chọn 9 số nguyên bất kỳ. Chứng minh có hai số có cùng số dư khi chia cho 8.
Gợi ý đáp án: lần lượt dùng 12 tháng; 10 lớp dư; 5 cặp số liên tiếp; 8 lớp dư.