Nguyên lý ngăn kéo của Dirichlet

Trong toán học, nguyên lý ngăn kéo, còn gọi là nguyên lý hộp hay nguyên lý Dirichlet, cho rằng nếu có n đối tượng được phân bố vào m chuồng và n > m, thì ít nhất một chuồng sẽ chứa nhiều hơn một đối tượng. Ví dụ thực tế là nếu có 3 găng tay, sẽ có ít nhất hai găng tay cùng loại (trái hoặc phải). Nguyên lý này có thể được dùng để chứng minh những tình huống bất ngờ như việc hai người có số lượng tóc trên đầu giống nhau trong một đám đông lớn hoặc nhận được rất nhiều thư rác trong hộp thư.

Người đầu tiên đề xuất nguyên lý này là nhà toán học Đức Johann Dirichlet, với tên gọi 'nguyên lý ngăn kéo' (Schubfachprinzip). Do đó, nguyên lý còn được biết đến với tên 'nguyên lý ngăn kéo Dirichlet' hoặc đơn giản là 'nguyên lý Dirichlet' (tên gọi này có thể gây nhầm lẫn với nguyên lý Dirichlet về hàm điều hòa). Trong một số ngôn ngữ như tiếng Pháp, tiếng Ý và tiếng Đức, nguyên lý này vẫn được gọi là 'ngăn kéo' thay vì 'chuồng bồ câu'.

Nguyên lý ngăn kéo Dirichlet thường được áp dụng 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 sử dụng cho các tập hợp vô hạn không thể ánh xạ một cách song ánh. Trong trường hợp này, nguyên lý có nội dung là: 'không tồn tại một ánh xạ đơn trên tập hợp hữu hạn nếu tập đích nhỏ hơn tập xác định'. Một số định lý trong toán học, như bổ đề Siegel, dựa trên nguyên lý này.

Mở rộng nguyên lý Dirichlet

Một cách mở rộng, nguyên lý ngăn kéo Dirichlet có thể được diễn đạt như sau:

Ghi chú:

• $\lceil <!--\; \lceil \; -->m/n\rceil <!--\; \rceil \; -->$ là phần nguyên làm tròn lên của phép chia m cho n, được tính bằng số nguyên nhỏ nhất lớn hơn hoặc bằng kết quả của phép chia m/n. Ví dụ $\lceil <!--\; \lceil \; -->3/4\rceil <!--\; \rceil \; -->=1$
• $\lfloor <!--\; \lfloor \; -->\; <div\; class="min-w-[250px]\; max-w-[94vw]\; md:max-w-[770px]">\; <ins\; class="adsbygoogle"\; style="display:block;\; text-align:center;"\; data-ad-layout="in-article"\; data-ad-format="fluid"\; data-ad-client="ca-pub-9247024304160346"\; data-ad-slot="4115752014"></ins>\; </div>m/n\rfloor <!--\; \rfloor \; -->$ là phần nguyên làm tròn xuống của phép chia m cho n, có giá trị bằng số nguyên lớn nhất nhỏ hơn hoặc bằng kết quả của phép chia m/n. Ví dụ $\lfloor <!--\; \lfloor \; -->3/4\rfloor <!--\; \rfloor \; -->=0$

Diễn giải theo 'ngôn ngữ' của xác suất thống kê

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

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

Đối với các tập hợp vô hạn

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

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

Các ví dụ tiêu biểu

Đếm số lượng tóc

Theo các nghiên cứu, mỗi người trung bình có khoảng từ 100.000 đến 150.000 sợi tóc. Do đó, tại Singapore với dân số hơn 3 triệu người, chắc chắn có ít nhất 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 còn gọi là luận đề ngày sinh, khám phá khả năng có một số người trong một nhóm ngẫu nhiên m người có cùng ngày sinh. Theo nguyên lý ngăn kéo Dirichlet, nếu số ngày trong năm là 366 (bao gồm cả ngày 29 tháng 2 trong năm nhuận), thì ít nhất có hai người sẽ có cùng ngày sinh.

Nếu áp dụng công thức , chỉ cần m = 57 thì xác suất có hai người trùng ngày sinh đã đạt đến 99%.

• Nguyên lý tổ hợp
• Tập hợp vô hạn Dedekind
• Nghịch lý Khách sạn Hilbert
• Định lý đa thức
• Định lý Ramsey
• Bằng chứng tổ hợp
• Định lý bơm cho ngôn ngữ chính quy

Ghi chú

• Grimaldi, Ralph P. Discrete and Combinatorial Mathematics: An Applied Introduction. ấn bản lần thứ 4. 1998. ISBN 0-201-19912-2. trang 244–248.
• Jeff Miller, Peter Flor, Gunnar Berg, và Julio González Cabillón. 'Nguyên lý chuồng bồ câu'. Trong Jeff Miller (biên tập) Những Sử Dụng Sớm Nhất của Một Số Thuật Ngữ Toán Học. Tài liệu điện tử, truy cập ngày 11 tháng 11 năm 2006.
• Leong Yu Kiang. Sống Cùng Toán Học. Ấn bản lần thứ 3. 2011. McGraw-Hill Education (Asia), Singapore. ISBN 978-007-132677-3

Các liên kết bên ngoài

• 'Trường hợp kỳ lạ của Nguyên lý Chuồng Bồ Câu'; Edsger Dijkstra nghiên cứu các cách giải thích và điều chỉnh của nguyên lý này.
• 'Nguyên lý Chuồng Bồ Câu'; Các ví dụ cơ bản về ứng dụng của nguyên lý này do Larry Cusick cung cấp.
• 'Nguyên lý Chuồng Bồ Câu từ Tạp chí Toán học và Đố Vui Tương Tác'; Phân tích và ví dụ cơ bản về Nguyên lý Chuồng Bồ Câu từ Alexander Bogomolny.
• 'Nguyên lý Chuồng Bồ Câu của Những Người Đam Mê Giải Đố'; Alexander Bogomolny bàn về vai trò của nguyên lý này trong lĩnh vực giải đố và phân tích.