Kiến thức về nguyên lý Dirichlet và ứng dụng của nó

Bài viết cung cấp một cái nhìn tổng quan về nguyên lý Dirichlet trong lý thuyết số và tập trung vào các ứng dụng quan trọng của nó trong các lĩnh vực như phân tích số và giải thuật số.

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

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ý này đã đượ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 được gọi là “nguyên lý quả cam” hay nguyên lý “chuồng chim bồ câu” hoặc “nguyên lý hộp (ngăn kéo) Dirichlet”.

Nội dung: 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.

Nếu đưa n vật thể vào m chuồng bồ câu với n > m, thì luôn có ít nhất 1 chuồng bồ câu sẽ có nhiều hơn 1 vật thể.

Ví dụ: Chẳng hạn nếu nhốt 10 con chim bồ câu vào 9 chuồng thì có ít nhất 1 chuồng chứa từ hai con bồ câu trở lên.

Hay có thể nói cách khác là không thể nhốt 7 chú thỏ vào 3 cái lồng sao cho mỗi lồng không quá 2 chú thỏ được.

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

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

1.1. Nguyên lý Dirichlet dạng 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ỏ.

1.2. 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 mở rộng cũng được chứng minh một cách dễ dàng.

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

1.4. 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 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 cùng một phần tử của B.

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

Ngoài ra, ta còn có nguyên lý Dirichlet vô hạn được phát biểu như sau:” Nếu chia một tập hợp vô hạn các quả táo vào hữu hạn các ngăn kéo thì phải có ít nhất một ngăn kéo chứa vô hạn quả táo.”

2. Bài tập ứng dụng nguyên lý Dirichlet lớp 9

Bài 1: Một trường học có 1000 học sinh gồm 23 lớp. Chứng minh rằng phải có ít nhất một lớp có từ 44 học sinh trở lên

Giả sử 23 lớp mỗi lớp có không quá 43 học sinh.

Khi đó số học sinh là:

43.23=989 học sinh (ít hơn 1000-989=11 học sinh)

Theo nguyên lí Dirichlet phải có ít nhất một lớp có từ 44 học sinh trở lên.

Bài 2: Một lớp có 50 học sinh. Chứng minh rằng có ít nhất 5 học sinh có tháng sinh giống nhau

Giả sử có không quá 4 học sinh có tháng sinh giống nhau

Một năm có 12 tháng, khi đó số học sinh của lớp có không quá: 12.4=48 (học sinh)

Theo nguyên lí Dirichlet phải có ít nhất 5 học sinh có tháng sinh giống nhau.

Trên đây là những kiến thức về nguyên lý Dirichlet và những điều bạn cần biết. Hy vọng sẽ giúp ích cho công việc và học tập của bạn. Bạn có thể tìm hiểu thêm một số kiến thức học tập khác trên VOH.