Nguyên lý Dirichlet, còn gọi là nguyên lý chuồng bồ câu, nói rằng nếu nhốt n + 1 con bồ câu vào n cái chuồng thì ít nhất một chuồng có từ hai con trở lên. Dạng tổng quát: xếp N vật vào k hộp thì có ít nhất một hộp chứa không dưới ⌈N/k⌉ vật, trong đó ⌈ ⌉ là phép làm tròn lên. Với 13 người, ít nhất hai người sinh cùng tháng; với 25 người, ít nhất ba người sinh cùng tháng, vì 25 chia 12 làm tròn lên là 3.
Nguyên lý nghe hiển nhiên đến mức nhiều người không tin nó là toán. Sức mạnh của nó nằm ở chỗ chứng minh một thứ tồn tại mà không cần chỉ ra thứ đó là gì, và cái khó không nằm ở nguyên lý mà ở chỗ chọn đúng chuồng. Bài đi qua phát biểu, chứng minh, cách chọn chuồng qua bốn ví dụ, và ứng dụng trong tin học như va chạm hàm băm hay giới hạn của nén dữ liệu.
Phát biểu, chứng minh và dạng tổng quát
Phát biểu cơ bản: nếu có N vật xếp vào k hộp với N > k, thì có ít nhất một hộp chứa từ hai vật trở lên. Chứng minh bằng phản chứng chỉ một dòng: giả sử mọi hộp chứa nhiều nhất một vật, thì tổng số vật nhiều nhất là k, mâu thuẫn với N > k. Nguyên lý thường được gắn với tên nhà toán học Đức Peter Gustav Lejeune Dirichlet ở thế kỷ 19, người dùng lập luận này trong lý thuyết số; tiếng Anh gọi là pigeonhole principle.
Dạng tổng quát: N vật xếp vào k hộp thì có một hộp chứa ít nhất ⌈N/k⌉ vật. Chứng minh vẫn bằng phản chứng: nếu mọi hộp chứa ít hơn ⌈N/k⌉, tức nhiều nhất ⌈N/k⌉ − 1 vật, thì tổng số vật nhiều nhất là k nhân (⌈N/k⌉ − 1), và đại lượng này nhỏ hơn N. Kiểm bằng số: N = 25, k = 12, ⌈25/12⌉ = 3; nếu mỗi tháng nhiều nhất 2 người thì tổng nhiều nhất là 24, không đủ 25.
Một cách diễn đạt khác hay gặp trong giáo trình: trung bình cộng của một nhóm số không thể lớn hơn số lớn nhất của nhóm. Nếu 25 người chia vào 12 tháng thì trung bình mỗi tháng hơn 2 người, nên có tháng ít nhất 3 người. Cách nhìn theo trung bình này giúp mở rộng sang những tình huống không phải vật và hộp rời rạc, ví dụ tổng độ dài các đoạn thẳng hay tổng diện tích các mảnh nằm trong một hình.
Cách chọn chuồng: phần khó nhất của mọi bài
Chuồng là các giá trị có thể có của một đặc trưng. Tháng sinh, số dư khi chia cho k, chữ số tận cùng, màu sắc, số người quen. Khi đề hỏi “chứng minh có hai cái giống nhau về X”, chuồng gần như luôn là tập các giá trị mà X có thể nhận.
Đếm chính xác số chuồng, kể cả trường hợp loại trừ nhau. Có bài số giá trị lý thuyết là n nhưng hai giá trị không thể cùng xuất hiện, nên thực chất chỉ còn n − 1 chuồng. Ví dụ về số người quen ở mục sau dùng đúng mẹo này.
Ghép cặp để tạo chuồng. Khi đề nói về tổng hoặc hiệu, nhóm các số thành cặp có tổng cố định; mỗi cặp là một chuồng. Chọn nhiều số hơn số cặp thì buộc phải lấy trọn một cặp.
Chia hình thành mảnh để tạo chuồng. Với bài hình học về khoảng cách, chia hình thành những mảnh nhỏ sao cho hai điểm bất kỳ trong cùng một mảnh đủ gần nhau. Kích thước mảnh do khoảng cách cần chứng minh quyết định.
Kiểm điều kiện “nhiều hơn”. Trước khi kết luận, so lại số vật với số chuồng. Số vật chỉ bằng số chuồng thì nguyên lý không cho gì cả: 12 người vẫn có thể sinh ở 12 tháng khác nhau.
Bốn ví dụ giải từng bước
Mỗi ví dụ dưới đây ghi rõ vật là gì, chuồng là gì, rồi mới áp nguyên lý. Đó cũng là cách trình bày nên dùng khi làm bài.
- Tổng bằng 11. Chọn 6 số khác nhau từ 1 đến 10, chứng minh có hai số có tổng bằng 11. Chuồng: năm cặp {1, 10}, {2, 9}, {3, 8}, {4, 7}, {5, 6}, mỗi số từ 1 đến 10 thuộc đúng một cặp. Vật: 6 số được chọn. Sáu vật, năm chuồng, nên có một cặp được chọn cả hai số, và hai số đó có tổng 11. Chọn 5 số thì không đủ: lấy 1, 2, 3, 4, 5 là không có cặp nào.
- Hiệu chia hết cho 5. Trong 6 số nguyên bất kỳ, có hai số mà hiệu chia hết cho 5. Chuồng: năm số dư 0, 1, 2, 3, 4 khi chia cho 5. Sáu số, năm số dư, nên có hai số cùng số dư, và hiệu của chúng chia hết cho 5.
- Năm điểm trong hình vuông. Đặt 5 điểm trong hình vuông cạnh 2, chứng minh có hai điểm cách nhau không quá căn bậc hai của 2, khoảng 1,41. Chia hình vuông thành 4 ô vuông cạnh 1. Năm điểm, bốn ô, nên có hai điểm cùng một ô, và khoảng cách giữa hai điểm trong ô vuông cạnh 1 không vượt quá đường chéo của ô, bằng căn bậc hai của 2.
- Số người quen. Trong một nhóm n người, với n từ 2 trở lên, có hai người quen số người bằng nhau, coi quen là quan hệ hai chiều. Mỗi người quen từ 0 đến n − 1 người, tức n giá trị. Nhưng 0 và n − 1 không thể cùng xuất hiện: nếu có người quen tất cả thì không ai quen 0 người. Vậy thực chất chỉ có n − 1 chuồng cho n người, nên có hai người cùng số người quen.
Để ý ba ví dụ đầu, chuồng được tạo bằng ba cách khác nhau: ghép cặp, số dư, chia hình. Ví dụ cuối dạy mẹo đếm lại số chuồng thực sự dùng được. Phần lớn bài tập Dirichlet trong giáo trình đại học là biến thể của bốn khuôn này.
Dạng tổng quát trong bài toán thực tế
Dạng ⌈N/k⌉ trả lời câu hỏi “ít nhất bao nhiêu”, rất hay gặp khi lên kế hoạch. Ví dụ giả định: một trường có 1.000 sinh viên năm nhất, cần biết chắc có ít nhất bao nhiêu người sinh cùng một ngày trong năm. Tính cả ngày 29 tháng 2 thì có 366 chuồng; ⌈1.000/366⌉ = 3, vì 366 nhân 2 bằng 732, nhỏ hơn 1.000. Vậy chắc chắn có ít nhất 3 sinh viên trùng ngày sinh, bất kể danh sách cụ thể ra sao.
Chiều ngược lại cũng dùng được: muốn chắc có ít nhất m vật trong cùng một hộp, cần tối thiểu bao nhiêu vật? Đáp số là k nhân (m − 1) cộng 1. Ví dụ giả định: một hộp có tất trắng, đen và xám lẫn lộn, bốc trong bóng tối. Muốn chắc có một đôi cùng màu, cần bốc 3 nhân 1 cộng 1 bằng 4 chiếc. Muốn chắc có 3 chiếc cùng màu, cần 3 nhân 2 cộng 1 bằng 7 chiếc. Lý do: với 6 chiếc vẫn có thể rơi đúng vào trường hợp mỗi màu 2 chiếc.
Đây là điểm khác cốt lõi giữa nguyên lý Dirichlet và xác suất. Nghịch lý ngày sinh nói rằng chỉ cần 23 người là xác suất có hai người trùng ngày sinh đã vượt một nửa, nhưng đó là khả năng, không phải chắc chắn. Dirichlet chỉ cho kết luận chắc chắn, nên con số nó đòi hỏi lớn hơn nhiều: phải 367 người mới chắc chắn có hai người trùng ngày sinh. Khi đọc một bài toán, xác định trước câu hỏi là “chắc chắn” hay “khả năng cao” để chọn đúng công cụ.
Nguyên lý chuồng bồ câu trong tin học
Hàm băm biến dữ liệu dài tuỳ ý thành một chuỗi có độ dài cố định, ví dụ 256 bit. Số đầu vào có thể có là vô hạn, còn số giá trị băm chỉ là 2 mũ 256, nên theo nguyên lý chuồng bồ câu, chắc chắn tồn tại hai đầu vào khác nhau cho cùng một giá trị băm, gọi là va chạm. Một hàm băm tốt không tránh được va chạm; nó chỉ làm cho việc tìm ra một va chạm khó đến mức không làm được trong thực tế. Bảng băm trong lập trình cũng vậy: số khoá nhiều hơn số ô thì phải có cơ chế xử lý va chạm.
Nén dữ liệu không mất mát cho kết quả bất ngờ hơn: không thuật toán nào nén được mọi tệp. Lập luận: có 2 mũ n tệp dài đúng n bit, trong khi tổng số tệp ngắn hơn n bit, kể cả tệp rỗng, là 1 + 2 + 4 + … + 2 mũ (n − 1), bằng 2 mũ n trừ 1. Số chuồng ít hơn số vật một đơn vị, nên nếu mọi tệp n bit đều được nén ngắn đi thì hai tệp khác nhau phải nén thành cùng một kết quả, và bộ giải nén không thể phân biệt chúng. Các chương trình nén chạy tốt vì dữ liệu thật có nhiều quy luật lặp, không phải vì vượt qua được phép đếm này.
Thêm một ứng dụng quen với người học thuật toán: trong một dãy n + 1 số lấy từ 1 đến n, chắc chắn có số lặp lại. Một số bài phỏng vấn lập trình dựa đúng trên nhận xét này để tìm phần tử trùng mà không cần sắp xếp dãy.
Dùng AI luyện bài Dirichlet: hỏi về chuồng, đừng hỏi đáp án
Với bài Dirichlet, kết luận thường chỉ là một câu “vậy có hai cái giống nhau”, nên chép lời giải không học được gì. Thứ cần luyện là con mắt chọn chuồng. Cách dùng AI hợp với mục tiêu đó:
- Đọc đề, tự trả lời ba câu trên giấy: vật là gì, chuồng là gì, mỗi loại có bao nhiêu. Chỉ khi bí ở câu thứ hai mới hỏi AI.
- Hỏi gợi ý thay vì lời giải. Câu lệnh mẫu: “Bài này dùng nguyên lý Dirichlet. Đừng giải. Chỉ gợi ý nên chọn chuồng theo đặc trưng nào, một câu thôi.”
- Khi AI đưa lời giải, kiểm hai điều: các chuồng có phủ hết mọi khả năng và không chồng lên nhau không; số vật có thật sự lớn hơn số chuồng không. Chatbot đôi khi chia hình thành mảnh mà khoảng cách trong mảnh lớn hơn mức cần chứng minh, hoặc đếm thiếu một chuồng.
- Thử tìm phản ví dụ cho trường hợp bớt đi một vật. Nếu đề dùng 6 số, xem 5 số có đủ không; nếu AI bảo 5 số cũng được mà bạn tìm ra phản ví dụ, lời giải của nó có vấn đề.
- Nhờ AI sinh biến thể: giữ khuôn ghép cặp nhưng đổi tổng, hoặc giữ khuôn số dư nhưng đổi số chia. Làm năm biến thể liên tiếp là đủ để nhận ra khuôn.
Nếu bạn ôn cho một kỳ thi, phòng thi thường không cho dùng thiết bị; luyện với AI ở nhà là để hiểu, còn khi làm bài bạn chỉ có cách chọn chuồng mà mình đã tập.
Câu hỏi thường gặp
Vì sao một nguyên lý hiển nhiên như vậy lại được học ở đại học?
Vì phần khó không nằm ở phát biểu mà ở việc nhận ra một bài toán là bài Dirichlet và chọn đúng chuồng. Nhiều kết quả trong lý thuyết số, tổ hợp, hình học và khoa học máy tính chứng minh được gọn nhờ nguyên lý này. Học nó là học một kiểu lập luận tồn tại, không cần xây dựng đối tượng cụ thể.
Nguyên lý Dirichlet có dùng được cho tập vô hạn không?
Có một dạng: nếu xếp vô hạn vật vào hữu hạn hộp thì có ít nhất một hộp chứa vô hạn vật. Dạng này dùng nhiều trong giải tích và tổ hợp vô hạn, ví dụ để rút ra dãy con có tính chất mong muốn từ một dãy bị chặn. Khi số hộp cũng vô hạn, nguyên lý không còn áp dụng trực tiếp.
Ký hiệu ⌈N/k⌉ nghĩa là gì, khác gì phần nguyên thông thường?
Đó là phần nguyên trên: số nguyên nhỏ nhất không nhỏ hơn N chia k. Ví dụ 25 chia 12 bằng khoảng 2,08 thì làm tròn lên là 3, còn phần nguyên dưới là 2. Khi N chia hết cho k, hai cách làm tròn cho cùng kết quả. Nhầm hai ký hiệu này là lỗi phổ biến khi tính số vật tối thiểu.
Nguyên lý Dirichlet có cho biết hộp nào chứa nhiều vật không?
Không. Nguyên lý chỉ khẳng định tồn tại ít nhất một hộp như vậy, không chỉ ra hộp nào và không cho biết có bao nhiêu hộp như thế. Đây là đặc trưng của chứng minh tồn tại không kiến thiết. Muốn tìm hộp cụ thể, bạn cần thêm thông tin hoặc một thuật toán duyệt.
Có phải bài nào yêu cầu chứng minh tồn tại cũng dùng Dirichlet không?
Không. Chứng minh tồn tại còn có nhiều cách: xây dựng trực tiếp, dùng định lý giá trị trung gian trong giải tích, lập luận cực hạn, phương pháp xác suất. Dirichlet hợp nhất với bài có nhiều đối tượng mà ít loại, hỏi về sự trùng lặp. Thấy cặp “nhiều vật, ít loại” là dấu hiệu tốt để thử nguyên lý này trước.