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

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm
Hình minh họa cho nguyên lý chuồng bồ câu. Có n = 10 con bồ câu trong m = 9 chuồng. Vì 10 lớn hơn 9 nên theo nguyên lý chuồng bồ câu, có ít nhất 1 chuồng chứa từ 2 con bồ câu trở lên.

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 Diritchlet 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ể.[1] Định lý này được minh họa trong thực tế bằng một số câu nói như "trong 2 găng tay, có ít nhất hai găng tay phải hoặc hai găng tay trái." It is an example of a counting argument, 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 1 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 1 số lượng cực lớn thư rác[1].

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ọm này có thể gây ra 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 Ý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 dượ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ạncodomain 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[sửa | sửa mã nguồn]

Nếu m vật thể đượ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 \lfloor m/n \rfloor vật thể nếu m là bội của n, và ít nhất \lfloor m/n \rfloor + 1 vật thể 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 \lceil m/n \rceil vật thể và ít nhất một hộp chứa sẽ mang không quá \lfloor m/n \rfloor vật thể.

Chú thích:

  • \lceil m/n \rceilphầ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ụ \lceil 3/4 \rceil = 1
  • \lfloor m/n \rfloorphầ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ụ \lfloor 3/4 \rfloor = 0

Diễn đạt theo "ngôn ngữ" xác suất thống kê[sửa | sửa mã nguồn]

Nếu m chim bồ câu được đặt vào n chuồng với xác suất đồng nhất là 1/n, thì ít nhất 1 chuồng bồ câu sẽ có hơn 1 con chim với xác suất như sau
1 - \frac{(n)_m}{n^m}, \!

với (n)mgiai thừa giảm n(n − 1)(n − 2)...(nm + 1). Với m = 0 và m = 1 (and n > 0), xác suất bằng không; nói cách khác, nếu chỉ có 1 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 (mn), 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 chm 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ê:

Nếu một biến ngẫu nhiên X giá trị trung bình hữu hạn E(X) thì xác suất X lớn hơn hay bằng E(X) là khác 0, và xác suất X nhỏ hơn hay bằng E(X) cũng khác 0.

Đ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 Xm/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[sửa | sửa mã nguồ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ố:

Nếu số phần tử của tập hợp A lớn hơn số phần tử của tập hợp B, thì không tồn tại phép nội xạ nào từ A đến B.

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 is sufficient to ensure that the cardinality increases.

Một số ví dụ[sửa | sửa mã nguồn]

Đếm tóc[sửa | sửa mã nguồn]

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ó 2 người có số sợi tóc giống hệt nhau.[1]

Nghịch lý ngày sinh[sửa | sửa mã nguồn]

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=367 thì ít nhất sẽ có 2 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 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%.

Xem thêm[sửa | sửa mã nguồn]

Chú thích[sửa | sửa mã nguồn]

  1. ^ a ă â Leong, tr. 50
  2. ^ Leong, tr. 52
  3. ^ Leong, tr. 51

Tham khảo[sửa | sửa mã nguồn]

Liên kết ngoài[sửa | sửa mã nguồn]