Nguyên_lý ngăn_kéo Dirichlet_Trong toán_học nguyên_lý chuồng bồ_câu nguyên_lý hộp hay nguyên_lý ngăn_kéo Dirichlet có nội_dung là nếu_như một số_lượng n vật_thể được đặt vào m chuồng bồ_câu với điều_kiện n m thì ít_nhất một chuồng bồ_câu sẽ có nhiều hơn 1 vật_thể Định_lý này được minh_hoạ trong thực_tế bằng một_số câu nói như trong 3 găng_tay có ít_nhất hai găng_tay phải hoặc hai găng tay_trái Đó là một ví_dụ của một đối_số đếm và mặc_dù trông có_vẻ trực_giác nhưng nó có_thể được dùng để chứng_minh về khả_năng xảy ra những sự_kiện không_thể ngờ tới tỉ_như 2 người có cùng một số_lượng sợi tóc trên đầu trong 1 đám đông lớn có một_số người mặc kiểu quần_áo giống nhau hoặc bất_thình_lình trong hộp_thư nhận được một số_lượng cực lớn thư rác Người đầu_tiên đề_xuất ra nguyên_lý này được cho là nhà toán_học Đức Johann_Dirichlet khi ông đề_cập tới nó với tên gọi nguyên_lý ngăn_kéo Schubfachprinzip_Vì vậy một tên gọi thông_dụng khác của nguyên_lý chuồng bồ_câu chính là nguyên_lý ngăn_kéo Dirichlet hay đôi_khi gọi gọn là nguyên_lý Dirichlet tên gọi gọn này có_thể gây ra nhầm_lẫn với nguyên_lý Dirichlet về hàm điều_hoà Trong một_số ngôn_ngữ như tiếng Pháp tiếng Ý và tiếng Đức nguyên_lý này cũng vẫn được gọi bằng tên ngăn_kéo chứ không phải chuồng bồ_câu Nguyên_lý ngăn_kéo Dirichlet được ứng_dụng trực_tiếp nhất cho các tập_hợp hữu_hạn hộp ngăn_kéo chuồng bồ_câu nhưng nó cũng có_thể được áp_dụng đối_với các tập_hợp vô_hạn không_thể được đặt vào song ánh Cụ_thể trong trường_hợp này nguyên_lý ngăn_kéo có nội_dung là không tồn_tại một đơn ánh trên những tập_hợp hữu_hạn mà codomain của nó nhỏ hơn tập xác_định của nó Một_số định_lý của toán_học như bổ_đề Siegel được xây_dựng trên nguyên_lý này Nguyên_lý Dirichlet mở_rộng Mở_rộng hơn_nữa ta có_thể viết nguyên_lý ngăn_kéo Dirichlet như sau Chú_thích BULLET formula _ 1 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ụ formula _ 2 BULLET formula _ 3 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ụ formula _ 4 Diễn_đạt theo ngôn_ngữ xác_suất thống_kê với n là giai thừa giảm 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 Đối_với tập_hợp vô_hạn 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 Một_số ví_dụ Đếm tóc 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 Nghịch_lý ngày_sinh 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 Nếu xét công_thức formula _ 5 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 Xem thêm BULLET Nguyên_lý tổ_hợp BULLET Tập_hợp vô_hạn Dedekind_BULLET_Nghịch lý Hilbert của Khách_sạn Lớn_BULLET_Định lý đa_thức BULLET Định_lý Ramsey_BULLET_Combinatorial proof BULLET Pumping lemma for regular languages Tham_khảo BULLET Grimaldi_Ralph_P_Discrete and Combinatorial_Mathematics_An_Applied Introduction 4th edn 1998 ISBN 0 201 19912 2 pp 244 248 BULLET 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 BULLET Leong_Yu_Kiang_Living with Mathematics 3rd Edition 2011 McGraw_Hill_Education_Asia Singapore ISBN 978 007 132677 3 Liên_kết ngoài BULLET The strange case of The_Pigeon hole Principle_Edsger_Dijkstra investigates interpretations and reformulations of the principle BULLET The_Pigeon_Hole_Principle Elementary examples of the principle in use by Larry_Cusick_BULLET_Pigeonhole Principle from Interactive_Mathematics_Miscellany and Puzzles basic Pigeonhole_Principle analysis and examples by Alexander_Bogomolny_BULLET_The Puzzlers_Pigeonhole_Alexander_Bogomolny on the importance of the principle in the field of puzzle solving and analysis
Nguyên_lý ngăn_kéo Dirichlet