Nguyên lý Dirichlet cơ bản
Nguyên lý “chuồng và thỏ” cho bài toán tồn tại: chọn đúng “thỏ”, “chuồng”; số dư, tháng sinh, màu sắc, chia đoạn thẳng; bài toán trường hợp xấu nhất.
1Bài giảng tư duy
Tại sao lại nghĩ ra hướng giải này? Có những bài chỉ hỏi “có tồn tại hay không” — chứng minh có hai bạn sinh cùng tháng, có hai số có hiệu chia hết cho 5… Ta không cần chỉ ra đó là ai, là số nào, chỉ cần chứng minh chắc chắn có. Công cụ mạnh nhất cho loại bài này là nguyên lý Dirichlet.
- Dạng cơ bản: nhốt \(n + 1\) con thỏ vào \(n\) cái chuồng thì có ít nhất một chuồng chứa từ 2 con trở lên.
- Dạng tổng quát: nhốt \(m\) con thỏ vào \(n\) chuồng, nếu \(m > k \cdot n\) thì có chuồng chứa ít nhất \(k + 1\) con.
- Chứng minh bằng phản chứng: nếu mọi chuồng có không quá \(k\) con thì tổng số thỏ không quá \(k \cdot n\) — mâu thuẫn.
Ba bước làm bài: (1) xác định “thỏ” (đối tượng cần xếp); (2) tạo “chuồng” (tháng sinh, màu, số dư khi chia cho n, đoạn thẳng nhỏ…) sao cho số chuồng ít hơn số thỏ; (3) hai “thỏ” chung một chuồng thì có tính chất đề cần. Ví dụ: hai số có cùng số dư khi chia cho \(n\) thì hiệu của chúng chia hết cho \(n\).
Bài toán “lấy ít nhất bao nhiêu”: hãy tưởng tượng mình rất xui — lấy theo cách tệ nhất có thể, rồi cộng thêm 1.
- Đề có chữ “chứng minh tồn tại”, “luôn có”, “chắc chắn có ít nhất…” → nghĩ tới Dirichlet.
- Đề hỏi “hai số có hiệu chia hết cho \(n\)” → chọn chuồng là các số dư khi chia cho \(n\) (có \(n\) chuồng).
- Đề hỏi “phải lấy ít nhất bao nhiêu để chắc chắn…” → xét trường hợp xấu nhất rồi cộng 1.
- Đề cho nhiều điểm trên một đoạn thẳng hay trong một hình → chia hình thành các phần nhỏ làm “chuồng”.
- Số chuồng không ít hơn số thỏ (ví dụ 5 số và 5 số dư) → không dùng được Dirichlet.
- Kết luận “mỗi chuồng đều có 2 thỏ” hoặc “có chuồng có đúng 2 thỏ” — nguyên lý chỉ cho “ít nhất”.
- Bài “lấy ít nhất”: quên rằng trường hợp xấu nhất có thể lấy hết cả một màu khác.
- Dùng sai phép tính: \(m\) thỏ, \(n\) chuồng thì phải so \(m\) với \(k \cdot n\), không phải với \(k + n\).
2Ví dụ nhiều cách giải
Chữ số tận cùng chỉ có thể là \(0, 1, 2, \ldots, 9\): 10 chuồng. Có 11 số (11 thỏ) mà chỉ 10 chuồng nên theo nguyên lý Dirichlet có hai số cùng chuồng, tức có cùng chữ số tận cùng. ∎
Chữ số tận cùng của một số chính là số dư khi chia số đó cho 10. 11 số mà chỉ có 10 số dư \(0, 1, \ldots, 9\) nên có hai số cùng số dư. Khi đó hiệu của chúng chia hết cho 10, nghĩa là hai số có cùng chữ số tận cùng. ∎
Xui nhất: lấy phải toàn bộ 10 chiếc đen trước. Lấy thêm 2 chiếc nữa thì cả 2 đều trắng. Vậy cần \(10 + 2 = 12\) chiếc. Nếu chỉ lấy 11 chiếc thì có thể chỉ được 1 chiếc trắng, nên 12 là ít nhất.
Muốn chắc chắn có 2 chiếc trắng, số tất đen bị lấy ra nhiều nhất là 10. Lấy \(n\) chiếc thì số chiếc trắng ít nhất là \(n - 10\). Cần \(n - 10 \ge 2\), tức \(n \ge 12\).
3Bài tập tự luận — gợi ý nhiều tầng
Làm ra giấy trước, rồi điền kết quả vào các mốc chấm bên dưới để máy chấm điểm (giống biểu điểm của giám khảo). Bí thì mở từng gợi ý một. Nếu xem lời giải trước khi nộp, bài vẫn được chấm thử nhưng không lưu điểm.
4Trắc nghiệm 15 câu — 3 tầng
- (1) Hai số đó có cùng số dư khi chia cho 5 nên hiệu của chúng chia hết cho 5.
- (2) Khi chia 6 số cho 5, chỉ có 5 số dư có thể là \(0, 1, 2, 3, 4\).
- (3) Theo nguyên lý Dirichlet, có hai số có cùng số dư.
- (4) Kết luận: có hai số có hiệu chia hết cho 5.
- Bước 1. Coi 12 tháng là 12 chuồng, 30 bạn là 30 thỏ.
- Bước 2. Giả sử mỗi tháng có nhiều nhất 2 bạn sinh ra.
- Bước 3. Khi đó cả lớp có nhiều nhất \(12 + 2 = 14\) bạn.
- Bước 4. Điều này mâu thuẫn với 30 bạn, nên có tháng có ít nhất 3 bạn sinh ra.