TÀI LIỆU HỌC TẬP: NGUYÊN LÝ DIRICHLET

Dành cho học sinh lớp 10

1. Giới thiệu

Nguyên lý Dirichlet, còn được biết đến với tên gọi "Nguyên lý chuồng bồ câu" hay "Nguyên lý n+1 con thỏ trong n lồng", là một trong những nguyên lý cơ bản và quan trọng trong Toán học rời rạc. Mặc dù phát biểu đơn giản, nguyên lý này lại có rất nhiều ứng dụng thú vị trong việc giải quyết các bài toán thuộc nhiều lĩnh vực khác nhau của Toán học, đặc biệt là Số học, Tổ hợp và Hình học.

Tài liệu này được biên soạn nhằm cung cấp cho các em học sinh lớp 10 một cái nhìn chi tiết và dễ hiểu về nguyên lý Dirichlet, các dạng bài toán thường gặp và phương pháp áp dụng nguyên lý này để giải quyết chúng.

2. Phát biểu nguyên lý

Nguyên lý Dirichlet có thể được phát biểu một cách tổng quát như sau:

Phát biểu 1 (Dạng đơn giản): Nếu có $n+1$ con thỏ nhốt trong $n$ cái lồng thì tồn tại ít nhất một lồng có ít nhất hai con thỏ.

Phát biểu 2 (Dạng tổng quát): Nếu có $k \cdot n + 1$ con thỏ nhốt trong $n$ cái lồng thì tồn tại ít nhất một lồng có ít nhất $k+1$ con thỏ.

• Chú ý:
  • "Con thỏ" và "lồng" chỉ là cách diễn đạt hình ảnh. Trong các bài toán cụ thể, "con thỏ" có thể là các đối tượng (số, điểm, đoạn thẳng,...), "lồng" có thể là các tập hợp, khoảng, vùng,...
  • Nguyên lý Dirichlet khẳng định sự tồn tại chứ không chỉ ra cách xác định cụ thể "lồng" nào chứa nhiều "thỏ" nhất.

3. Chứng minh

• Chứng minh Phát biểu 1:

  Giả sử phản chứng, không có lồng nào chứa ít nhất 2 con thỏ. Điều này có nghĩa là mỗi lồng chứa tối đa 1 con thỏ. Vì có $n$ lồng nên số thỏ tối đa có thể chứa là $n$, mâu thuẫn với giả thiết có $n+1$ con thỏ. Vậy, tồn tại ít nhất một lồng chứa ít nhất 2 con thỏ.

• Chứng minh Phát biểu 2:

  Giả sử phản chứng, không có lồng nào chứa ít nhất $k+1$ con thỏ. Điều này có nghĩa là mỗi lồng chứa tối đa $k$ con thỏ. Vì có $n$ lồng nên số thỏ tối đa có thể chứa là $n \cdot k$, mâu thuẫn với giả thiết có $k \cdot n + 1$ con thỏ. Vậy, tồn tại ít nhất một lồng chứa ít nhất $k+1$ con thỏ.

4. Các dạng bài toán thường gặp và ví dụ

4.1. Dạng 1: Bài toán số học

Ví dụ 1: Chứng minh rằng trong 13 số nguyên bất kỳ luôn tồn tại hai số có cùng số dư khi chia cho 12.

Lời giải:

• "Thỏ": 13 số nguyên.
• "Lồng": 12 số dư có thể khi chia cho 12 (từ 0 đến 11).
• Theo nguyên lý Dirichlet, tồn tại ít nhất một "lồng" chứa ít nhất 2 "thỏ", tức là tồn tại ít nhất hai số có cùng số dư khi chia cho 12.

Ví dụ 2: Chứng minh rằng trong 5 số nguyên dương bất kỳ nhỏ hơn 9, luôn tìm được hai số có tổng bằng 10.

Lời giải:

• "Thỏ": 5 số nguyên dương.

• "Lồng": Các cặp số có tổng bằng 10: {1, 9}, {2, 8}, {3, 7}, {4, 6}, {5}. (5 cặp)

• Theo nguyên lý Dirichlet, tồn tại ít nhất một "lồng" chứa ít nhất 2 "thỏ". Tuy nhiên, cặp {5} chỉ có 1 số, nên phải tồn tại hai số khác thuộc một trong bốn cặp còn lại. Do đó, tồn tại hai số có tổng bằng 10.

4.2. Dạng 2: Bài toán hình học

Ví dụ 3: Cho 5 điểm bất kỳ nằm trong một hình vuông có cạnh bằng 2. Chứng minh rằng tồn tại hai điểm có khoảng cách không vượt quá $\sqrt{2}$.

Lời giải:

• Chia hình vuông thành 4 hình vuông nhỏ có cạnh bằng 1.
• "Thỏ": 5 điểm.
• "Lồng": 4 hình vuông nhỏ.
• Theo nguyên lý Dirichlet, tồn tại ít nhất một hình vuông nhỏ chứa ít nhất 2 điểm.
• Khoảng cách lớn nhất giữa hai điểm trong một hình vuông nhỏ là độ dài đường chéo, bằng $\sqrt{1^2 + 1^2} = \sqrt{2}$. Vậy, tồn tại hai điểm có khoảng cách không vượt quá $\sqrt{2}$.

Ví dụ 4: Trong một hình tròn bán kính 1, ta lấy 7 điểm bất kỳ. Chứng minh rằng luôn tìm được hai điểm có khoảng cách không vượt quá 1.

Lời giải:

• Chia hình tròn thành 6 hình quạt bằng nhau (mỗi hình quạt có góc ở tâm là 60 độ).
• "Thỏ": 7 điểm.
• "Lồng": 6 hình quạt.
• Theo nguyên lý Dirichlet, tồn tại ít nhất một hình quạt chứa ít nhất 2 điểm.
• Khoảng cách lớn nhất giữa hai điểm trong một hình quạt là 1 (khi chúng nằm trên hai bán kính của hình quạt và cách nhau một góc 60 độ). Vậy, tồn tại hai điểm có khoảng cách không vượt quá 1.

4.3. Dạng 3: Bài toán tổ hợp

Ví dụ 5: Chứng minh rằng trong một nhóm 6 người bất kỳ, luôn tồn tại 3 người quen nhau đôi một hoặc 3 người không quen nhau đôi một.

Lời giải:

• Chọn một người, gọi là A. Trong 5 người còn lại, chia thành hai nhóm:

  • Nhóm 1: Những người quen A.
  • Nhóm 2: Những người không quen A.

• Theo nguyên lý Dirichlet, một trong hai nhóm này có ít nhất 3 người. Giả sử nhóm 1 có ít nhất 3 người (gọi là B, C, D).

  • Nếu có hai người trong B, C, D quen nhau, giả sử B và C quen nhau, thì A, B, C là 3 người quen nhau đôi một.
  • Nếu không có hai người nào trong B, C, D quen nhau thì B, C, D là 3 người không quen nhau đôi một.

  Tương tự cho trường hợp nhóm 2 có ít nhất 3 người.

5. Bài tập tự luyện

1. Chứng minh rằng trong 10 số có hai chữ số bất kỳ, luôn tìm được hai số có hiệu là một số có hai chữ số giống nhau.
2. Chứng minh rằng trong 7 số thực bất kỳ, luôn tìm được hai số $x$ và $y$ sao cho $0 \leq \frac{x-y}{1+xy} \leq \frac{1}{\sqrt{3}}$.
3. Cho 9 điểm nằm trong một tam giác đều có cạnh bằng 1. Chứng minh rằng tồn tại hai điểm có khoảng cách không vượt quá $\frac{1}{2}$.
4. Trong một hình vuông cạnh 1 người ta lấy 51 điểm phân biệt. Chứng minh rằng tồn tại ba điểm trong số đó nằm trong một hình tròn có bán kính không lớn hơn $\frac{1}{7}$.
5. Chứng minh rằng trong $n+1$ số tự nhiên khác nhau không vượt quá $2n$, luôn tìm được hai số nguyên tố cùng nhau.

6. Kết luận

Nguyên lý Dirichlet là một công cụ mạnh mẽ để giải quyết nhiều bài toán khác nhau trong Toán học. Việc nắm vững nguyên lý này và các dạng bài tập thường gặp sẽ giúp các em học sinh tự tin hơn trong quá trình học tập và giải bài. Hy vọng tài liệu này sẽ là nguồn tham khảo hữu ích cho các em. Chúc các em học tốt!