Nguyên lý Dirichlet và ứng dụng

Câu trả lời đúng nhất:

Nguyên lý Dirichlet do nhà toán học người Đức nổi tiếng Johann Peter Gustav Lejeune Dirichlet (1805-1859) đề xuất từ thế kỷ XX.

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

Nguyên lý Diruchlet đã được ứng dụng để chứng minh sự tồn tại nghiệm trong nhiều bài toán tổ hợp.

Để hiểu rõ hơn về Nguyên lí Dirichlet và ứng dụng, Top lời giải mời các bạn đọc bài viết sau.

1. Nguyên lý Dirichlet là gì?

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.

Ví 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 ).

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

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

2. Ứng dụng nguyên lý Dirichlet

Nguyên lý Diruchlet đã được áp dụng để chứng minh sự tồn tại nghiệm trong nhiều bài toán tổ hợp.

3. Phân loại nguyên lý Dirichlet

- 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 hai con thỏ.

Nguyên lí Dirichlet (Đi-rích-lê) tưởng chừng đơn giản như vậy, nhưng nó là một công cụ rất hiệu quả dùng để chứng minh nhiều kết quả sâu sắc của toán học. Nó có áp dụng trong nhiều lĩnh vực khác nhau của toán học.

- Nguyên lý Dirichlet dạng 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à  con thỏ, ở đây kí hiệu [α] để chỉ phần nguyên của số α.

- Nguyên lí Dirichlet dưới dạng tập hợp

Nguyên lí Dirichlet thực chất là một định lí về tập hữu hạn. Người ta có thể phát biểu nguyên lí này dưới dạng tập hợp như sau:

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.

4. Một số điểm cần lưu ý để giải các bài toán bằng nguyên lý Dirichlet

a. Các bài toán áp dụng nguyên tắc Điriclê thường là các bài toán chứng minh sự tồn tại của sự vật, sự việc mà không cần phải chỉ ra một cách tường minh sự vật, sự việc đó.

b. Nhiều bài toán, nguyên tắc Điriclê chỉ xuất hiện sau khi biến đổi qua một bước trung gian, hoặc thành lập các dãy số mới.

c. Để giải bài toán áp dụng nguyên tắc Điriclê, nhiều khi ta phải kết hợp với phương pháp chứng minh phản chứng.

d. Khi giải các bài toán mà ta đã biết phải áp dụng nguyên tắc Điriclê hoặc dự đoán sẽ phải dùng nguyên tắc này, chúng ta cần suy nghĩ hoặc biến đổi bài toán để làm xuất hiện khái niệm "thỏ" và "lồng", khái niệm "nhốt thỏ vào lồng".

e. Cũng có thể có những bài toán phải áp dụng 2, 3 lần nguyên tắc Điriclê.

f. Trong suy nghĩ khi giải toán ta cố gắng làm xuất hiện các khái niệm "thỏ" và "lồng", nhưng trong trình bày phần lời giải ta cố gắng diễn đạt theo ngôn ngữ toán học thông thường

g. Khi giải xong các bài toán áp dụng nguyên tắc Điriclê, chúng ta cố gắng suy nghĩ để sáng tạo ra được các bài toán tổng quát hơn hoặc cụ thể hơn. Vì chỉ có như thế ta mới thật nắm chắc bài toán mà mình đã làm.

5. Ứng dụng nguyên lý Dirichlet

Nguyên lý Diruchlet đã được áp dụng để chứng minh sự tồn tại nghiệm trong nhiều bài toán tổ hợp.

----------------------

Trên đây Top lời giải đã mang đến phần trả lời cho câu hỏi “Nguyên lý dirichlet và ứng dụng” cũng như một số kiến thức mở rộng về Nguyên lý Dirichlet. Chúng tôi hi vọng với những kiến thức trên bạn có thể học tập tốt hơn. Hẹn gặp bạn ở câu hỏi tiếp theo.