Nguyên lý Dirichlet nói rằng nếu nhốt nhiều thỏ hơn số chuồng thì chắc chắn có ít nhất một chuồng chứa từ hai con trở lên. Điều này hiển nhiên tới mức ai cũng gật, nhưng dùng khéo thì nó chứng minh được chuyện như ở Hà Nội có hai người có số sợi tóc bằng nhau, mà không cần đếm tóc ai cả.
Chào bạn, đây là Nhà Toán Học. Đây là một trong những công cụ được dạy sớm nhất cho học sinh thi học sinh giỏi, và cũng là công cụ dễ làm người ta ngạc nhiên nhất. Tập này mình kể nó từ ngăn kéo tất tới hình học, và chỉ cho bạn chỗ khó thật sự của nó.
Phát biểu đơn giản và cái tên Dirichlet
Phát biểu gốc ngắn gọn: có nhiều đồ vật hơn số ngăn thì có một ngăn chứa ít nhất hai đồ vật. Trong tiếng Anh người ta gọi là nguyên lý chuồng bồ câu, còn sách Việt Nam quen gọi theo tên nhà toán học Đức Dirichlet ở thế kỷ mười chín, người dùng nó trong các nghiên cứu về số.
Có một dạng mạnh hơn: nếu có nhiều hơn ka nhân en đồ vật bỏ vào en ngăn, thì có ngăn chứa ít nhất ka cộng một đồ vật. Ví dụ một trường có bốn trăm học sinh, chắc chắn có ít nhất hai bạn trùng ngày sinh, vì một năm chỉ có tối đa ba trăm sáu mươi sáu ngày.
Điểm lạ của nguyên lý này là nó chỉ khẳng định có, mà không nói đó là ai. Mình biết chắc có hai bạn trùng ngày sinh nhưng không biết hai bạn nào. Toán học gọi kiểu này là chứng minh tồn tại.
Nhiều người thấy kiểu chứng minh đó hơi ăn gian. Nhưng trong rất nhiều bài, biết chắc có là đủ, việc tìm cụ thể là chuyện khác.
Ví dụ ngăn kéo tất: cần bốc bao nhiêu chiếc?
Sáng sớm cúp điện, ngăn kéo có tất trắng và tất đen để lẫn. Bạn phải bốc ít nhất bao nhiêu chiếc để chắc chắn có một đôi cùng màu. Câu trả lời là ba.
Ở đây chuồng là màu, có hai chuồng là trắng và đen. Thỏ là những chiếc tất bốc ra. Bốc ba chiếc vào hai chuồng thì có một chuồng chứa hai chiếc, tức có một đôi cùng màu.
Đổi câu hỏi một chút: phải bốc bao nhiêu chiếc để chắc chắn có một đôi màu trắng, biết ngăn có mười chiếc đen. Lúc này trường hợp xấu nhất là bạn bốc trúng cả mười chiếc đen trước, nên phải bốc mười hai chiếc.
Hai câu hỏi nghe na ná nhưng đáp án khác xa nhau. Khi làm bài Dirichlet, hãy luôn hỏi trường hợp xấu nhất là gì. Đáp án chính là trường hợp xấu nhất cộng thêm một.
Vì sao chắc chắn có hai người cùng số sợi tóc?
Con số hay được nhắc là trên đầu một người có khoảng một trăm nghìn sợi tóc, có người nhiều hơn. Dù vậy, khó có ai tới một triệu sợi. Coi mỗi con số từ không tới một triệu là một chuồng, mình có khoảng một triệu chuồng.
Hà Nội có hàng triệu người, nhiều hơn một triệu khá xa. Mỗi người được xếp vào chuồng ứng với số sợi tóc của mình. Người nhiều hơn chuồng, nên có ít nhất một chuồng chứa hai người, tức là hai người có số sợi tóc bằng nhau đúng tới từng sợi.
Lập luận này không cần đếm tóc ai, cũng không cần biết số tóc chính xác của người nhiều tóc nhất. Chỉ cần một chặn trên đủ an toàn cho số tóc, và biết dân số vượt xa chặn đó.
Đây là kiểu suy luận rất đặc trưng của toán: thay vì đi tìm câu trả lời cụ thể, mình chứng minh câu trả lời phải tồn tại bằng cách so hai số lượng.
Dirichlet trong hình học: năm điểm trong một hình vuông
Bài cổ điển: trong một hình vuông cạnh hai mét, đặt năm điểm bất kỳ. Chứng minh có hai điểm cách nhau không quá căn bậc hai của hai mét, tức khoảng một mét bốn mươi mốt.
Chỗ khó là không ai cho sẵn chuồng, mình phải tự dựng. Chia hình vuông thành bốn hình vuông nhỏ cạnh một mét. Năm điểm, bốn ô, nên có một ô nhỏ chứa ít nhất hai điểm.
Trong một hình vuông cạnh một mét, hai điểm xa nhau nhất là hai đầu đường chéo, dài đúng căn bậc hai của hai. Vậy hai điểm cùng ô cách nhau không quá con số đó. Xong bài.
Bạn thấy đấy, cả bài nằm ở câu chia hình vuông thành bốn. Nguyên lý thì ai cũng biết, cái tài là nhìn ra chuồng ở đâu. Các thầy dạy đội tuyển thường nói học Dirichlet là học cách chọn chuồng.
Những lỗi hay gặp và cách luyện
Lỗi thứ nhất là chọn số chuồng lớn hơn số thỏ rồi vẫn kết luận. Nguyên lý chỉ dùng được khi thỏ nhiều hơn chuồng, nên trước khi viết, hãy đếm cả hai.
Lỗi thứ hai là chọn chuồng mà một đồ vật có thể nằm ở hai chuồng cùng lúc, ví dụ điểm nằm đúng trên đường chia. Phải quy ước rõ điểm trên đường chia thuộc ô nào, nếu không lập luận có kẽ hở.
Cách luyện tốt nhất là làm nhiều bài với cùng một câu hỏi tự đặt: đâu là thỏ, đâu là chuồng, có bao nhiêu mỗi loại. Khi câu hỏi này thành phản xạ, các bài Dirichlet tự nhiên dễ lên trông thấy.
Câu đố nhỏ: chứng minh trong bất kỳ nhóm sáu người nào, luôn có ba người đôi một quen nhau, hoặc ba người đôi một không quen nhau. Gợi ý, bắt đầu từ một người và năm người còn lại.
Câu hỏi thường gặp
Nguyên lý Dirichlet học ở lớp mấy?
Nguyên lý này thường được giới thiệu trong các chuyên đề bồi dưỡng học sinh giỏi từ lớp sáu, lớp bảy. Phát biểu rất dễ hiểu, nhưng bài tập có thể khó tới mức xuất hiện trong đề thi quốc gia và quốc tế.
Vì sao gọi là nguyên lý chuồng bồ câu?
Hình ảnh gốc là nhiều chim bồ câu bay vào ít ô chuồng hơn, thì có ô phải chứa hơn một con. Sách Việt Nam hay đổi thành thỏ và chuồng, ý nghĩa không đổi.
Nguyên lý Dirichlet có cho biết chính xác ô nào chứa nhiều không?
Không. Nó chỉ khẳng định có ít nhất một ô như vậy. Muốn biết ô nào thì phải có thêm thông tin về cách các đồ vật được xếp.
Dirichlet có dùng được ngoài đời không?
Có, theo kiểu ước lượng nhanh. Ví dụ một kho có hàng nghìn mã hàng mà mã chỉ có ba chữ số thì chắc chắn có mã bị trùng. Người làm hệ thống mã hoá và lưu trữ dữ liệu gặp đúng câu hỏi này rất thường xuyên.
Bài sáu người quen nhau có tên riêng không?
Có, nó là ví dụ mở đầu cho một nhánh toán gọi là lý thuyết Ramsey, nghiên cứu việc trong một hệ đủ lớn thì luôn xuất hiện một trật tự nào đó. Con số sáu là nhỏ nhất, với năm người thì có cách sắp xếp không có bộ ba nào như vậy.
