NGUYÊN LÝ DIRICHLET

Ngày đăng: 09/08/2023

Trong phần Số học, nguyên tắc Dirichlet là một phần rất hay và được đưa vào nhiều trong các kì thi học sinh giỏi các cấp. Để có một tài liệu hữu ích cho các bạn sinh viên muốn tìm hiểu về nguyên tắc này chúng ta sẽ cùng nhau tóm tắt lại các cách phát biểu của nguyên lý Dirichlet và nêu ra các ứng dụng cơ bản của nó.


Hiện nay, Toán học là một trong những bộ môn quan trọng đối với mỗi học sinh, sinh viên. Nó giúp cho các bạn nâng cao năng lực, phẩm chất trí tuệ, giúp phát triển khả năng tư duy và nhạy bén, rèn luyện được tính sáng tạo, logic và trừu tượng. Toán học gồm nhiều thành phần cấu tạo nên và số học được xem là một trong những thành phần quan trọng và lâu đời nhất của toán học. Số học không chỉ là một lĩnh vực của toán học lí thuyết mà còn là lĩnh vực có nhiều ứng dụng, đặc biệt trong lĩnh vực bảo mật thông tin. Vì thế việc trang bị các kiến thức cơ bản về số học ngay từ trường phổ thông là hết sức cần thiết. 

   Trong phần Số học, nguyên tắc Dirichlet là một phần rất hay và được đưa vào nhiều trong các kì thi học sinh giỏi các cấp. Để có một tài liệu hữu ích cho các bạn sinh viên muốn tìm hiểu về nguyên tắc này chúng ta sẽ cùng nhau tóm tắt lại các cách phát biểu của nguyên lý Dirichlet và nêu ra các ứng dụng cơ bản của nó. 

1. Nguyên lý Dirichlet cơ bản:

   - 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.

   - Nguyên lí Dirichlet tuy có phát biểu đơn giản nhưng lại được vận dụng rất nhiều trong thực tế. Nhờ nguyên lí này mà trong nhiều trường hợp, người ta dễ dàng chứng minh được sự tồn tại mà không đưa ra được phương pháp tìm kiếm cụ thể.


NGUYÊN LÝ DIRICHLET

Ví dụ 1: Một lớp học có 42 học sinh được xếp thành 4 hàng không phân biệt nam nữ thì lớp đó có ít nhất hai hàng bị lẽ số học sinh.

Ví dụ 2: Trong ví có tổng số tiền 1000000VNĐ thì ta sẽ có ít nhất hai tờ tiền có mệnh giá giống nhau.

Ví dụ 3: Trên một đoạn đường sẽ có ít nhất hai ngôi nhà cùng cấp với nhau.


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


   Nếu nhốt hết n con thỏ vào m ≥ 2 cái chuồng thì tồn tại một chuồng có ít nhất là n+m-1m con thỏ, ở đây kí hiệu [α] để chỉ phần nguyên của số α.

   Ta chứng minh nguyên lý Dirichlet mở rộng như sau: Giả sử trái lại mọi chuồng thỏ không có đến n+m-1m=n-1m+1=n-1m+1 con, thì số thỏ trong chuồng đều nhỏ hơn hoặc bằng n-1m con. Từ đó suy ra tổng số con thỏ không vượt quá n – 1 con. Điều này vô lý vì có n con thỏ.

Ví dụ 1: Có một 100 cây giống đem trồng vào 3 mảnh đất, thì tồn tại trong một mãnh đất sẽ là 34 cây giống.

 Ví dụ 2: Có 5 con thỏ được nhốt vào 3 chuồng thì tồn tại một chuồng có ít nhất là 2 con thỏ.

Ví dụ 3: 200kg gạo được phát cho 7 hộ gia đình thì tồn tại 1 hộ có ít nhất là 29kg gạo.

  1. Nguyên lý Dirichlet dạng tập hợp:

   Cho A và B là hai tập hợp khác rỗng có số phần tử hữu hạn, mà số lượng phần tử của A lớn hơn số lượng phần tử của B. Nếu với một quy tắc nào đó, mỗi phần tử của A cho tương ứng với một phần tử của B, thì tồn tại ít nhất hai phần tử khác nhau của A mà chúng tương ứng với một phần tử của B.


NGUYÊN LÝ DIRICHLET

Ví dụ 1: Một trận đấu bóng có 5 đội tham gia thi đấu sẽ luôn tồn tại 2 đội có số điểm ghi bàn bằng nhau.

Ví dụ 2: Trong một cuộc họp có 10 ý tưởng thì sẽ luôn tồn tại 2 ý tưởng bị trung lập.

Ví dụ 3: Trong một 1000 nhân viên may theo sản lượng sẽ luôn tồn tại ít nhất 2 nhân viên may có cùng sản lượng .

  1.  Nguyên lý Dirichlet dạng tập hợp mở rộng:


   Giả sử A, B là hai tập hợp hữu hạn và S(A), S(B) tương ứng kí hiệu là các số lượng phần tử của A và B. Giả sử có một số tự nhiên k nào đó mà S(A) > k.S(B) và ta có quy tắc cho tương ứng với mỗi phần tử của A với một phần tử của B. Khi đó tồn tại ít nhất k+1 phần tử của A mà chúng tương ứng với phần tử của B

Chú ý: Khi k = 1 ta có ngay lại nguyên lý Dirichlet.


Bùi Hùng Vương - KCNTT

Các tin khác

Tuyển sinh Đai học
thac si cntt
Tuyển sinh Tiến sĩ
ĐẠI HỌC NTT
Trung tâm Thư viện