Nguyên Lý Đi-rich-lê Là Gì? Cho Ví Dụ?P/s: Nhanh Mình Tick - Olm

  - Nguyên lý Dirichlet do nhà toán học người Đức nổi tiếng là Dirichlet đề xuất từ thế kỷ XX đã được áp dụng để chứng minh sự tồn tại nghiệm trong nhiều bài toán tổ hợp. Nguyên lý này được phát triển từ một mệnh đề rất đơn giản gọi là nguyên lý “nguyên lý quả cam” hay là nguyên lý  “chuồng chim bồ câu”: Giả sử có một đàn chim bồ câu bay vào chuồng. Nếu số chim nhiều hơn số ngăn chuồng thì chắc chắn có ít nhất một ngăn có nhiều hơn một con chim.                                                    

         - Một cách tổng quát, nguyên lý Dirichlet được phát biểu như sau:

      Nếu xếp nhiều hơn n+1 đối tượng vào n cái hộp thì tồn tại ít nhất một hộp chứa không ít hơn hai đối tượng.

     - Việc chứng minh nguyên lý này có thể tiến hành bằng lập luận phản chứng rất đơn giản: Giả sử không hộp nào chứa nhiều hơn một đối tượng thì chỉ có nhiều nhất là n đối tượng được xếp trong các hộp, trái với giả thiết là số đối tượng lớn hơn n.

vVí dụ 1:

         Một năm có nhiều nhất là 365 ngày. Do vậy trong số 366 người bất kỳ bao giờ cũng có ít nhất 2 người có cùng ngày sinh nhật ( không xét năm nhuận ).

vVí dụ 2:

        Thang điểm bài kiểm tra là từ 0 đến 10, tức là có 11 thang điểm khác nhau. Do vậy trong số 12 sinh viên bất kỳ của một lớp sẽ có ít nhất 2 người có kết quả bài kiểm tra giống nhau.

vVí dụ 3:

         Cấp bậc quân hàm của sĩ quan có 8 cấp bậc từ thiếu úy đến đại tá. Do vậy trong một đơn vị có 9 sĩ quan thì sẽ có ít nhất 2 người cùng cấp bậc.

·      Nguyên lý Dirichlet cơ bản:

       Nếu nhốt n+1 con thỏ vào n cái chuồng thì bao giờ cũng có một chuồng chứa ít nhất 2 con thỏ.

·      Nguyên lý Dirichlet mở rộng:

      Nếu nhốt n con thỏ vào cái chuồng thì tồn tại một chuồng có ít nhất  con thỏ .

     Ở đây kí hiệu  để chỉ phần nguyên của .

      Ta có thể chứng minh nguyên lý Dirichlet mở rộng như sau: Giả sử mọi chuồng thỏ không có đến  ==(con)

                thì số thỏ trong mỗi chuồng đều nhỏ hơn hoặc bằng  con. Từ đó suy ra tổng số con thỏ không vượt quá  con. Điều này vô lý vì có n con thỏ. Vậy giả thiết phản chứng là sai. Nguyên lý Dirichlet mở rộng được chứng minh.