Nguyên lý ngăn kéo Dirichlet

“	Nếu m con chim bồ câu được đặt vào n chuồng chim bồ câu và m > n, thì (ít nhất) một chuồng chim bồ câu sẽ bao hàm ít nhất ${\displaystyle \lfloor m/n\rfloor }$ con chim bồ câu nếu m là bội của n, và ít nhất ${\displaystyle \lfloor m/n\rfloor +1}$ con chim bồ câu nếu m không phải là bội của n.	”
— [2]

Mở rộng hơn nữa, ta có thể viết nguyên lý ngăn kéo Dirichlet như sau:

“

Nếu m vật thể được đặt vào n hộp chứa, thì ít nhất một hộp chứa sẽ mang không dưới ${\displaystyle \lfloor m/n\rfloor }$ vật thể và ít nhất một hộp chứa sẽ mang không quá ${\displaystyle \lceil m/n\rceil }$ vật thể.

”

Chú thích:

• ${\displaystyle \lceil m/n\rceil }$ là phần nguyên trần của phép tính m chia cho n, có giá trị bằng số nguyên nhỏ nhất có giá trị lớn hơn hay bằng kết quả của phép tính m/n. Ví dụ ${\displaystyle \lceil 3/4\rceil =1}$
• ${\displaystyle \lfloor m/n\rfloor }$ là phần nguyên sàn của phép tính m chia cho n, có giá trị bằng số nguyên lớn nhất có giá trị nhỏ hơn hay bằng kết quả của phép tính m/n. Ví dụ ${\displaystyle \lfloor 3/4\rfloor =0}$

với (n)_m là giai thừa giảm n(n − 1)(n − 2)...(n − m + 1). Với m = 0 và m = 1 (và n > 0), xác suất bằng không; nói cách khác, nếu chỉ có một con chim thì sẽ không có chuyện nhiều chim ở chung 1 chuồng. Với m > n (số chim nhiều hơn số chuồng) thì chắc chắn sẽ có chuyện "chung đụng", trong trường hợp này nó trùng khớp với nguyên lý chuồng bồ câu nguyên bản. Nhưng mà ngay cả khi số chim không vượt quá số chuồng (m ≤ n), do tính ngẫu nhiên của việc xếp chim vào chuồng, vẫn có khả năng nhiều chim sẽ phải ở chung 1 chuồng với nhau. Ví dụ nếu 2 chim được xếp vào 4 chuồng thì vẫn có 25% khả năng 2 chim này ở chung chuồng, với 5 chim và 10 chuồng thì khả năng có nhiều chim trong 1 chuồng là 69.76%; và với 10 chim - 20 chuồng thì con số này là 93.45%. Nếu số chuồng chim không đổi, thì dĩ nhiên xác suất nhiều chim ở trong 1 chuồng sẽ càng tăng khi tổng số chim càng tăng. Vấn đề này được xem xét ở quy mô lớn hơn trong nghịch lý ngày sinh.

Một dạng mở rộng khác của nguyên lý này theo ngôn ngữ xác suất thống kê:

Điều này có nghĩa là, đặt m chim bồ câu vào n chuồng và gọi X là số chim trong 1 tổ được chọn ngẫu nhiên. Giá trị trung bình của X là m/n, vì vậy nếu số chim nhiều hơn số chuồng thì giá trị trung bình của X sẽ lớn hơn 1. Vì vậy, tồn tại khả năng X có giá trị lớn hơn 2.

Nguyên lý ngăn kéo Dirichlet có thể được mở rộng để ứng dụng cho tập hợp vô hạn bằng cách diễn dạt lại theo thuật ngữ của cơ số:

Tuy nhiên theo cách viết này, nguyên lý Dirichlet mang tính chất lặp thừa, bởi vì rõ ràng nếu số phần tử của tập A lớn hơn tập B thì đương nhiên không có phép nội xạ nào từ A sang B cả. Điều khiến cho trường hợp tập vô hạn trở nên thú vị là, nó cung cấp thêm ít nhất một yếu tố cho một tập hợp là đủ để đảm bảo rằng sự gia tăng lực lượng.

Theo các nghiên cứu, trung bình mỗi người chỉ có chừng 100.000 đến 150.000 sợi tóc. Như vậy, ví dụ, ở Singapore có dân số hơn 3 triệu người thì ít nhất sẽ có 61 người có số lượng sợi tóc giống hệt nhau.^[1]

Nghịch lý ngày sinh hay luận đề ngày sinh đề cập đến khả năng về một số người có chung 1 ngày sinh trong 1 đám đông m người được chọn ngẫu nhiên. Theo nguyên lý ngăn kéo Dirichlet, ví dụ, nếu n=366 thì ít nhất sẽ có hai người có chung 1 ngày sinh (số ngày trong năm là 366 ngày, tính cả ngày 29 tháng 2 của năm nhuận).^[3]

Nếu xét công thức ${\displaystyle 1-{\frac {(n)_{m}}{n^{m}}}\!}$ thì chỉ cần m = 57 là xác suất hai người có chung 1 ngày sinh đã lên tới 99%.

• Nguyên lý tổ hợp
• Tập hợp vô hạn Dedekind
• Nghịch lý Hilbert của Khách sạn Lớn
• Định lý đa thức
• Định lý Ramsey
• Combinatorial proof
• Pumping lemma for regular languages

• Grimaldi, Ralph P. Discrete and Combinatorial Mathematics: An Applied Introduction. 4th edn. 1998. ISBN 0-201-19912-2. pp. 244–248.
• Jeff Miller, Peter Flor, Gunnar Berg, and Julio González Cabillón. "Pigeonhole principle". In Jeff Miller (ed.) Earliest Known Uses of Some of the Words of Mathematics. Electronic document, retrieved ngày 11 tháng 11 năm 2006.
• Leong Yu Kiang. Living with Mathematics. 3rd Edition. 2011. McGraw-Hill Education (Asia), Singapore. ISBN 978-007-132677-3

• "The strange case of The Pigeon-hole Principle"; Edsger Dijkstra investigates interpretations and reformulations of the principle.
• "The Pigeon Hole Principle"; Elementary examples of the principle in use by Larry Cusick.
• "Pigeonhole Principle from Interactive Mathematics Miscellany and Puzzles"; basic Pigeonhole Principle analysis and examples by Alexander Bogomolny.
• "The Puzzlers' Pigeonhole"; Alexander Bogomolny on the importance of the principle in the field of puzzle solving and analysis.