Tóm tắt nội dung: Nguyên lý Dirichlet (nguyên lý chuồng bồ câu) là một công cụ tổ hợp cơ bản nhưng cực kỳ mạnh mẽ trong giải toán học sinh giỏi quốc gia và quốc tế. Bài viết giới thiệu dạng cơ bản, dạng mở rộng của nguyên lý cùng hệ thống các bài toán áp dụng tiêu biểu có lời giải chi tiết.
I. Nguyên lý Dirichlet
Nguyên lý Dirichlet (tiếng Anh: the pigeonhole principle, còn gọi là the drawer principle) ở dạng đơn giản nhất được phát biểu đầu tiên bởi nhà toán học G. Lejeune Dirichlet (1805–1859):
"Nếu nhốt \(n + 1\) con thỏ vào \(n\) cái chuồng (\(n \in \mathbb{N}^*\)) thì luôn có (ít nhất là) hai con thỏ bị nhốt trong cùng một chuồng."
Một cách tổng quát, ta có nguyên lý Dirichlet mở rộng:
"Nếu nhốt \(m\) con thỏ vào \(n\) cái chuồng (\(m, n \in \mathbb{N}^*\)) thì luôn tồn tại một chuồng chứa ít nhất là \(1 + \left[\frac{m - 1}{n}\right]\) con thỏ."
Ở đây, ký hiệu \([a]\) được dùng để chỉ phần nguyên của số thực \(a\), tức là số nguyên lớn nhất không vượt quá \(a\).
II. Một số bài toán áp dụng
Bài 1 (Putnam 1993): Cho một dãy số gồm 19 số nguyên dương không vượt quá 93 và một dãy số gồm 93 số nguyên dương không vượt quá 19. Chứng minh rằng từ hai dãy số đó ta có thể lần lượt trích ra hai dãy con có tổng các số hạng bằng nhau.
Hướng dẫn - Bài toán tổng quát:
Cho hai dãy (hữu hạn) các số nguyên dương:
\[x_1 \le x_2 \le \dots \le x_m \le n, \quad y_1 \le y_2 \le \dots \le y_n \le m.\]Khi đó, luôn tồn tại các chỉ số \(1 \le i_1 \le i_2 \le m\) và \(1 \le j_1 \le j_2 \le n\) sao cho:
\[\sum_{i=i_1}^{i_2} x_i = \sum_{j=j_1}^{j_2} y_j.\]Bài 2 (Trích đoạn kết luận): Chứng minh tồn tại hai tập con có hiệu các tổng nghịch đảo sai khác nhau bé hơn \(\frac{1}{1000}\).
Theo nguyên lý Dirichlet, tồn tại hai tập con khác nhau có tổng nghịch đảo các phần tử thuộc vào cùng một nửa khoảng. Loại bỏ khỏi hai tập con đó các phần tử chung (hai tập con 7-phần tử khác nhau thì có tối đa 6 phần tử chung), ta sẽ thu được hai tập con \(k\)-phần tử (với \(k\) nguyên dương, \(k \le 7\)) thoả yêu cầu của bài toán: hiệu của hai tổng nghịch đảo các phần tử trong hai tập con này sẽ sai khác nhau ít hơn \(\frac{1}{1000}\).
Bài 3 (Iberoamerica 1998): Các đại diện của \(n\) quốc gia (\(n \in \mathbb{N}^* \setminus \{1\}\)) ngồi quanh một bàn tròn theo cách sao cho hai người ngồi sát bên phải hai đại diện bất kỳ với cùng quốc tịch thì phải có quốc tịch khác nhau. Hãy xác định (theo \(n\)) số lớn nhất có thể các đại diện ngồi quanh bàn tròn đó.
Lời giải:
Ta sẽ dùng \(X_1, X_2, \dots, X_n\) để ký hiệu \(n\) quốc gia có đại diện ngồi tại bàn tròn; các đại diện có quốc tịch \(X_i\) (\(\mathbb{N}^* \ni i \le n\)) sẽ được đánh số là \(x_i^1, x_i^2, \dots\)
1. Đánh giá chặn trên:
Trước tiên, nếu có nhiều hơn \(n^2\) đại diện ngồi tại bàn tròn, thì theo nguyên lý Dirichlet tồn tại \(i\) (\(\mathbb{N}^* \ni i \le n\)) để quốc gia \(X_i\) có ít nhất là \(n + 1\) đại diện, mà ta ký hiệu là \(x_i^1, x_i^2, \dots, x_i^{n+1}\); nhưng chỉ có \(n\) quốc tịch, nên vẫn theo nguyên lý Dirichlet, trong số \(n + 1\) người ngồi sát bên phải các đại diện \(x_i^1, x_i^2, \dots, x_i^{n+1}\), phải có hai người có cùng quốc tịch; mâu thuẫn với yêu cầu của bài toán.
Mâu thuẫn đó chứng tỏ rằng có không quá \(n^2\) đại diện ngồi tại bàn tròn.
2. Chỉ ra cấu hình đạt giá trị lớn nhất:
Tiếp theo, giả sử mỗi quốc gia có đúng \(n\) đại diện: các đại diện của \(X_i\) (\(\mathbb{N}^* \ni i \le n\)) là \(x_i^1, x_i^2, \dots, x_i^n\); ta sẽ chỉ ra rằng quy nạp theo \(n\) rằng có một cách sắp xếp toàn bộ \(n^2\) đại diện đó vào bàn tròn sao cho mọi yêu cầu của bài toán đều được thoả mãn.
Mỗi cách sắp xếp toàn bộ \(n^2\) đại diện vào bàn tròn thực chất là một hoán vị
\[(a_1, a_2, \dots, a_{n^2-1}, a_{n^2}) \tag{1}\]của tập hợp \(\{x_i^j \mid i, j \in \mathbb{N}^*;\, i, j \le n\}\) với quy ước rằng trong cách sắp xếp này:
- \(a_{k+1}\) là đại diện ngồi sát bên phải \(a_k\) (với mọi \(k\) nguyên dương mà \(k < n^2\))
- \(a_1\) ngồi sát bên phải \(a_{n^2}\)
(ta đồng nhất các hoán vị có thể thu được từ nhau qua một phép hoán vị vòng quanh).
Khi \(n = 2\) dễ thấy cách sắp xếp \((x_1^1, x_1^2, x_2^1, x_2^2)\) thoả mãn mọi yêu cầu của bài toán. Giả sử với \(n \in \mathbb{N}^* \setminus \{1\}\) nào đó đã có một cách sắp xếp, mà ta vẫn giữ ký hiệu (1), thoả mãn mọi yêu cầu của bài toán. Khi đó, có thể chứng minh rằng:
Với mỗi \(i \in \mathbb{N} \cap [1, n]\), tồn tại duy nhất \(j \in \mathbb{N} \cap [1, n]\) sao cho người ngồi sát bên phải \(x_i^j\) cũng có quốc tịch \(X_i\).
Thật vậy, nếu \(n\) người ngồi sát bên phải các đại diện \(x_i^1, x_i^2, \dots, x_i^n\) đều có quốc tịch khác \(X_i\) (chỉ có \(n - 1\) quốc tịch như thế), thì theo nguyên lý Dirichlet, ít nhất hai người trong số họ phải có cùng quốc tịch; mâu thuẫn với yêu cầu của bài toán. Mâu thuẫn này chứng tỏ sự tồn tại của \(j = j_i\). Hơn nữa, nếu \(\mathbb{N} \cap [1; n] \ni k \ne j_i\), thì theo yêu cầu của bài toán - người ngồi sát bên phải \(x_i^k\) sẽ không cùng quốc tịch \(X_i\) với người ngồi sát bên phải \(x_i^j\). Điều đó cho thấy tính duy nhất của \(j_i\).
Vậy số lớn nhất các đại diện có thể ngồi quanh bàn tròn là \(n^2\).