Nguyên lý Dirichlet: Định lý, công thức và bài tập chi tiết

Nguyên lý Dirichlet (hay còn gọi là nguyên lý chuồng bồ câu) là một trong những nguyên lý quan trọng nhất trong toán học tổ hợp. Bài viết này sẽ trình bày chi tiết nguyên lí Dirichlet, định lý Dirichlet cùng các dạng bài tập và phương pháp áp dụng nguyên lý này một cách hiệu quả nhất.

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

Trước tiên, chúng ta cần hiểu rõ nguyên lý Dirichlet là gì và nguồn gốc của nó:

1.1. Giới thiệu về Dirichlet

Dirichlet (Johann Peter Gustav Lejeune Dirichlet, 1805-1859) là nhà toán học người Đức, có nhiều đóng góp quan trọng trong lý thuyết số và giải tích. Nguyên lý Dirichlet được đặt theo tên ông, mặc dù ý tưởng này đã được biết đến từ trước.

1.2. Định nghĩa nguyên lý Dirichlet (Dạng cơ bản)

Nguyên lí Dirichlet phát biểu đơn giản như sau:

“Nếu có \( n + 1 \) con chim được nhốt vào \( n \) cái lồng, thì tồn tại ít nhất một lồng chứa ít nhất 2 con chim.”

Hay viết dưới dạng toán học:

Nếu \( n + 1 \) đối tượng được phân vào \( n \) nhóm, thì tồn tại ít nhất một nhóm chứa ít nhất 2 đối tượng.

1.3. Ý nghĩa trực quan

Định lý Dirichlet tuy đơn giản nhưng vô cùng mạnh mẽ:

Thuật ngữ	Trong nguyên lý	Ý nghĩa
Chim (Pigeons)	Đối tượng cần phân loại	Các phần tử, số, điểm,…
Lồng (Pigeonholes)	Các nhóm/hộp chứa	Các tập hợp, lớp, khoảng,…
Kết luận	Có lồng chứa ≥ 2 chim	Tồn tại nhóm có ≥ 2 phần tử

2. Các dạng phát biểu của Nguyên lý Dirichlet

Nguyên lý Dirichlet có nhiều dạng phát biểu khác nhau, từ đơn giản đến tổng quát:

2.1. Dạng 1: Nguyên lý Dirichlet cơ bản

Nếu \( n + 1 \) đối tượng được xếp vào \( n \) hộp, thì có ít nhất một hộp chứa ít nhất 2 đối tượng.

2.2. Dạng 2: Nguyên lý Dirichlet tổng quát

Nếu \( m \) đối tượng được xếp vào \( n \) hộp, thì có ít nhất một hộp chứa ít nhất \( \left\lceil \frac{m}{n} \right\rceil \) đối tượng.

Trong đó \( \left\lceil x \right\rceil \) là hàm trần (ceiling function) – số nguyên nhỏ nhất lớn hơn hoặc bằng \( x \).

Ví dụ: Nếu 25 học sinh được chia vào 7 nhóm, thì có ít nhất một nhóm có ít nhất \( \left\lceil \frac{25}{7} \right\rceil = \left\lceil 3.57 \right\rceil = 4 \) học sinh.

2.3. Dạng 3: Nguyên lý Dirichlet mở rộng (Dạng ngược)

Nếu \( m \) đối tượng được xếp vào \( n \) hộp, thì có ít nhất một hộp chứa không quá \( \left\lfloor \frac{m}{n} \right\rfloor \) đối tượng.

Trong đó \( \left\lfloor x \right\rfloor \) là hàm sàn (floor function) – số nguyên lớn nhất nhỏ hơn hoặc bằng \( x \).

2.4. Bảng tóm tắt các dạng

Dạng	Điều kiện	Kết luận
Cơ bản	\( n + 1 \) đối tượng, \( n \) hộp	Có hộp chứa ít nhất 2 đối tượng
Tổng quát	\( m \) đối tượng, \( n \) hộp	Có hộp chứa ít nhất \( \left\lceil \frac{m}{n} \right\rceil \) đối tượng
Dạng ngược	\( m \) đối tượng, \( n \) hộp	Có hộp chứa không quá \( \left\lfloor \frac{m}{n} \right\rfloor \) đối tượng

3. Cách áp dụng Nguyên lý Dirichlet

Để áp dụng nguyên lí Dirichlet hiệu quả, cần thực hiện theo các bước sau:

3.1. Phương pháp giải bài toán

Bước 1: Xác định “chim” (đối tượng cần xét)

Bước 2: Xác định “lồng” (cách phân loại đối tượng)

Bước 3: Đếm số “chim” và số “lồng”

Bước 4: Áp dụng nguyên lý Dirichlet để kết luận

3.2. Kỹ thuật xác định “lồng”

Đây là bước quan trọng nhất khi áp dụng định lý Dirichlet:

Loại bài toán	Cách xác định “lồng”
Bài toán số dư	Các lớp số dư khi chia cho n
Bài toán khoảng cách	Chia đoạn thành các khoảng nhỏ
Bài toán chọn số	Ghép cặp số có tổng/hiệu cố định
Bài toán điểm	Chia vùng thành các ô nhỏ

3.3. Dấu hiệu nhận biết bài toán Dirichlet

Các dấu hiệu thường gặp trong bài toán áp dụng nguyên lý Dirichlet:

• “Chứng minh tồn tại…”
• “Chứng minh có ít nhất…”
• “Chọn \( n + 1 \) phần tử từ tập \( n \) phần tử…”
• “Trong số các… có ít nhất hai…”
• “Bất kỳ… nào cũng có…”

4. Các dạng bài tập Nguyên lý Dirichlet

Để vận dụng thành thạo nguyên lý Dirichlet, cần nắm các dạng bài sau:

4.1. Dạng 1: Bài toán số dư

Đặc điểm: Liên quan đến phép chia lấy dư, tính chất chia hết.

Phương pháp:

1. Xét các số dư khi chia cho \( n \): có \( n \) số dư là \( 0, 1, 2, …, n-1 \)
2. “Lồng” là các lớp số dư
3. Áp dụng nguyên lí Dirichlet

4.2. Dạng 2: Bài toán tổng và hiệu

Đặc điểm: Chứng minh tồn tại hai số có tổng/hiệu thỏa điều kiện.

Phương pháp:

1. Ghép các cặp số có tổng/hiệu cố định
2. “Lồng” là các cặp số đã ghép
3. Áp dụng định lý Dirichlet

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

Đặc điểm: Liên quan đến điểm, đoạn thẳng, khoảng cách.

Phương pháp:

1. Chia vùng thành các ô/phần nhỏ
2. “Lồng” là các ô/phần đã chia
3. Áp dụng nguyên lý Dirichlet

4.4. Dạng 4: Bài toán dãy số

Đặc điểm: Liên quan đến dãy số, tổng các phần tử liên tiếp.

Phương pháp:

1. Xét các tổng riêng phần \( S_1, S_2, …, S_n \)
2. Xét số dư của các tổng riêng phần
3. Áp dụng nguyên lý để tìm hai tổng có cùng số dư

5. Ví dụ và bài tập minh họa

Dưới đây là các ví dụ minh họa cách áp dụng nguyên lý Dirichlet chi tiết:

Ví dụ 1: Bài toán cơ bản về số dư

Đề bài: Chứng minh rằng trong 13 số nguyên bất kỳ, luôn tồn tại 2 số có hiệu chia hết cho 12.

Lời giải:

Bước 1: Xác định “chim” và “lồng”

• “Chim”: 13 số nguyên đã cho
• “Lồng”: 12 lớp số dư khi chia cho 12 (gồm 0, 1, 2, …, 11)

Bước 2: Áp dụng nguyên lý Dirichlet

Có 13 số (chim) và 12 lớp số dư (lồng).

Theo nguyên lí Dirichlet: tồn tại ít nhất 2 số có cùng số dư khi chia cho 12.

Bước 3: Kết luận

Gọi hai số đó là \( a \) và \( b \) với \( a \equiv b \pmod{12} \)

Khi đó: \( a – b \equiv 0 \pmod{12} \), tức là \( (a – b) \vdots 12 \)

Vậy trong 13 số nguyên bất kỳ, luôn tồn tại 2 số có hiệu chia hết cho 12. ∎

Ví dụ 2: Bài toán về ngày sinh

Đề bài: Trong một lớp học có 35 học sinh. Chứng minh rằng có ít nhất 3 học sinh sinh cùng tháng.

Lời giải:

Bước 1: Xác định “chim” và “lồng”

• “Chim”: 35 học sinh
• “Lồng”: 12 tháng trong năm

Bước 2: Áp dụng nguyên lý Dirichlet dạng tổng quát

Có 35 học sinh và 12 tháng.

Theo định lý Dirichlet: tồn tại ít nhất một tháng có ít nhất \( \left\lceil \frac{35}{12} \right\rceil = \left\lceil 2.92 \right\rceil = 3 \) học sinh.

Vậy có ít nhất 3 học sinh sinh cùng tháng. ∎

Ví dụ 3: Bài toán hình học

Đề bài: Trong một hình vuông cạnh 2, người ta đặt 5 điểm. Chứng minh rằng tồn tại 2 điểm có khoảng cách không quá \( \sqrt{2} \).

Lời giải:

Bước 1: Xác định “chim” và “lồng”

Chia hình vuông cạnh 2 thành 4 hình vuông nhỏ cạnh 1.

• “Chim”: 5 điểm
• “Lồng”: 4 hình vuông nhỏ

Bước 2: Áp dụng nguyên lý Dirichlet

Có 5 điểm và 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.

Bước 3: Tính khoảng cách lớn nhất trong hình vuông nhỏ

Khoảng cách lớn nhất giữa 2 điểm trong hình vuông cạnh 1 là đường chéo = \( \sqrt{1^2 + 1^2} = \sqrt{2} \)

Vậy tồn tại 2 điểm có khoảng cách không quá \( \sqrt{2} \). ∎

Ví dụ 4: Bài toán dãy số

Đề bài: Cho \( n \) số nguyên dương \( a_1, a_2, …, a_n \). Chứng minh rằng tồn tại một số \( k \) liên tiếp trong dãy có tổng chia hết cho \( n \).

Lời giải:

Bước 1: Xét các tổng riêng phần

Đặt \( S_i = a_1 + a_2 + … + a_i \) với \( i = 1, 2, …, n \)

Bước 2: Xét số dư của các tổng riêng phần khi chia cho \( n \)

Có \( n \) tổng \( S_1, S_2, …, S_n \) và \( n \) số dư có thể: \( 0, 1, 2, …, n-1 \)

Trường hợp 1: Nếu tồn tại \( S_k \equiv 0 \pmod{n} \)

Thì \( a_1 + a_2 + … + a_k \) chia hết cho \( n \). (đpcm)

Trường hợp 2: Nếu không có \( S_i \) nào chia hết cho \( n \)

Thì \( n \) tổng \( S_1, S_2, …, S_n \) có số dư thuộc \( \{1, 2, …, n-1\} \) (có \( n-1 \) giá trị).

Theo nguyên lý Dirichlet: tồn tại \( i < j \) sao cho \( S_i \equiv S_j \pmod{n} \)

Khi đó: \( S_j – S_i = a_{i+1} + a_{i+2} + … + a_j \equiv 0 \pmod{n} \)

Vậy tồn tại một số phần tử liên tiếp có tổng chia hết cho \( n \). ∎

Ví dụ 5: Bài toán chọn số

Đề bài: Từ tập \( \{1, 2, 3, …, 2n\} \), chọn ra \( n + 1 \) số. Chứng minh rằng trong các số được chọn, tồn tại 2 số mà số này chia hết số kia.

Lời giải:

Bước 1: Biểu diễn mỗi số dạng \( 2^k \cdot m \) với \( m \) lẻ

Mỗi số từ 1 đến \( 2n \) có thể viết dạng \( 2^k \cdot m \) với \( m \) lẻ và \( m \in \{1, 3, 5, …, 2n-1\} \)

Bước 2: Xác định “chim” và “lồng”

• “Chim”: \( n + 1 \) số được chọn
• “Lồng”: \( n \) số lẻ từ 1 đến \( 2n-1 \) (đó là phần lẻ \( m \) của mỗi số)

Bước 3: Áp dụng nguyên lý Dirichlet

Theo định lý Dirichlet: tồn tại 2 số trong \( n + 1 \) số được chọn có cùng phần lẻ \( m \).

Giả sử đó là \( a = 2^p \cdot m \) và \( b = 2^q \cdot m \) với \( p < q \).

Khi đó: \( b = 2^{q-p} \cdot a \), nên \( a | b \).

Vậy tồn tại 2 số mà số này chia hết số kia. ∎

Ví dụ 6: Bài toán thực tế

Đề bài: Trong một nhóm 367 người, chứng minh rằng có ít nhất 2 người sinh cùng ngày trong năm (giả sử năm có 366 ngày).

Lời giải:

• “Chim”: 367 người
• “Lồng”: 366 ngày trong năm

Theo nguyên lý Dirichlet cơ bản (với \( n + 1 = 367 \), \( n = 366 \)):

Tồn tại ít nhất một ngày có ít nhất 2 người sinh.

Vậy có ít nhất 2 người sinh cùng ngày. ∎

Ví dụ 7: Bài toán nâng cao

Đề bài: Chứng minh rằng trong 52 số nguyên bất kỳ, tồn tại 2 số có tổng hoặc hiệu chia hết cho 100.

Lời giải:

Bước 1: Xét số dư khi chia cho 100

Mỗi số nguyên có số dư khi chia cho 100 thuộc \( \{0, 1, 2, …, 99\} \)

Bước 2: Ghép cặp các số dư

Ta ghép các số dư thành các cặp có tổng = 100:

• Cặp 0: \( \{0\} \) (đứng riêng)
• Cặp 50: \( \{50\} \) (đứng riêng vì 50 + 50 = 100)
• Các cặp: \( \{1, 99\}, \{2, 98\}, …, \{49, 51\} \) (có 49 cặp)

Tổng cộng có: \( 1 + 1 + 49 = 51 \) “lồng”

Bước 3: Áp dụng nguyên lý Dirichlet

Có 52 số và 51 “lồng”.

Theo nguyên lí Dirichlet: tồn tại 2 số rơi vào cùng một “lồng”.

• Nếu cùng thuộc lồng \( \{0\} \): hiệu chia hết cho 100
• Nếu cùng thuộc lồng \( \{50\} \): tổng chia hết cho 100
• Nếu cùng thuộc cặp \( \{k, 100-k\} \): hoặc cùng số dư (hiệu chia hết cho 100) hoặc khác số dư (tổng chia hết cho 100)

Vậy tồn tại 2 số có tổng hoặc hiệu chia hết cho 100. ∎

Bài tập tự luyện

Hãy thử sức với các bài tập sau để củng cố kiến thức về nguyên lý Dirichlet:

Bài	Đề bài	Gợi ý
1	Trong 27 số nguyên, chứng minh tồn tại 2 số có hiệu chia hết cho 26	Lồng = 26 lớp số dư
2	Trong tam giác đều cạnh 1, đặt 5 điểm. CMR tồn tại 2 điểm cách nhau không quá 0.5	Chia tam giác thành 4 tam giác nhỏ
3	Trong 100 số nguyên dương, CMR tồn tại một số các số liên tiếp có tổng chia hết cho 100	Xét tổng riêng phần
4	Trong 50 số tự nhiên đôi một khác nhau không vượt quá 99, CMR tồn tại 2 số có tổng bằng 99	Ghép cặp có tổng = 99
5	Lớp có 25 học sinh, mỗi học sinh chọn 3 trong 6 môn học. CMR có ít nhất 5 học sinh chọn cùng 3 môn	Lồng = số cách chọn 3 từ 6 = \( C_6^3 = 20 \)

6. Mẹo ghi nhớ và áp dụng Nguyên lý Dirichlet

Để vận dụng nguyên lý Dirichlet hiệu quả:

Mẹo	Nội dung
Nhận dạng	Tìm từ khóa: “tồn tại”, “ít nhất”, “chứng minh có”
Xác định lồng	Đây là bước quan trọng nhất – cần sáng tạo trong việc chia nhóm
Đếm đúng	Đảm bảo số chim > số lồng (hoặc đủ lớn)
Kết luận	Từ 2 phần tử cùng lồng suy ra tính chất cần chứng minh

7. Kết luận

Qua bài viết này, chúng ta đã tìm hiểu chi tiết về nguyên lý Dirichlet – một trong những nguyên lý quan trọng nhất trong toán học tổ hợp. Định lý Dirichlet tuy đơn giản trong phát biểu nhưng có ứng dụng rộng rãi trong nhiều bài toán.

Để vận dụng tốt nguyên lí Dirichlet, học sinh cần nhớ:

• Dạng cơ bản: \( n + 1 \) đối tượng vào \( n \) hộp → có hộp chứa ít nhất 2
• Dạng tổng quát: \( m \) đối tượng vào \( n \) hộp → có hộp chứa ít nhất \( \left\lceil \frac{m}{n} \right\rceil \)
• Bước quan trọng nhất là xác định “lồng” phù hợp với bài toán
• Thường gặp trong bài toán về số dư, khoảng cách, chọn số

Nguyên lý Dirichlet là công cụ mạnh mẽ giúp giải quyết nhiều bài toán tổ hợp và là kiến thức nền tảng cho các kỳ thi học sinh giỏi.