Nguyên lý Dirichlet hay còn được gọi là nguyên lý chuồng thỏ được phát biểu dưới dạng sau:”Có $n+1$ con thỏ được nhốt vào $n$ cái chuồng thì có một chuồng chứa ít nhất hai con thỏ“. Với nội dung khá đơn giản tuy nhiên nguyên lý này giúp giải được khá nhiều bài toán trong nhiều phân môn: đại số, số học, hình học, tổ hợp. Trong bài viết nhỏ này trình bày một vài ví dụ áp dụng nguyên lý Dirichlet giúp các bạn định hướng tốt hơn trong việc giải các bài toán.

1. Các ví dụ

a) Nguyên lý Dirichlet trong các bài toán đại số và số học

Nguyên lý Dirichlet có thể được phát biểu như sau: Có $n+1$ số tự nhiên lớn hơn $k$ và nhỏ hơn $k+n+1$, thì sẽ có 2 số bằng nhau.

Trong phát biểu trên ta xem $n+1$ số tự nhiên là $n+1$ con thỏ, các số tự nhiên lớn hơn $k$, nhỏ hơn $k+n+1$ gồm $k+1, k+2, \dots, k+n$ là $n$ cái chuồng. Khi đó chắc chắn có 2 con thỏ cùng một chuồng, hay sẽ có hai số bằng nhau.

Việc phát hiện đối tượng nào là thỏ, đối tượng nào là chuồng là một việc có ý nghĩa quan trọng, hoặc đôi khi ta phải xây dựng chuồng, thỏ, từ đó giải quyết vấn đề. Ta xét các ví dụ sau:

Ví dụ 1: Cho 676 số tự nhiên phân biệt không lớn hơn 2016. Chứng minh rằng chọn được hai số $a, b$ thỏa $|a-b| \in \left\{ 3, 6 \right\} $.

Ví dụ 2: Cho tập $A = {1, 2, 3, …, 9}$. Lấy $S$ gồm các phần tử thuộc $A$ sao cho tổng hai số bất kì thuộc $S$ là các số phân biệt. Hỏi tập $S$ có số phần tử nhiều nhất là bao nhiêu? Tại sao?

Ví dụ 3: Cho $1010$ số nguyên dương $a_1 < a_2 < …< a_{1010} \leq 2017$. Chứng minh rằng có $2$ số $a_i, a_k$ sao cho $a_i+a_1 = a_k$.

Nguyên lý áp dụng trong các bài toán số học được phát biểu dưới dạng sau: “Cho $n+1$ số nguyên, khi đó có 2 số có hiệu chia hết cho $n$“.

Ví dụ 4: Chứng minh rằng trong $11$ số chính phương thì có $2$ số có hiệu chia hết cho $20$.

Ví dụ 5: Cho $5$ số nguyên dương và mỗi số chỉ có ước nguyên tố là $2$ và $3$. Chứng minh rằng có $2$ số mà tích là một số chính phương.

Ví dụ 6: Xét $20$ số tự nhiên $1, 2, . . . , 20$. Hãy tìm số nguyên dương $k$ nhỏ nhất sao cho với mỗi cách lấy $k$ số phân biệt từ $20$ số trên đều lấy được hai số $a, b$ sao cho $a + b$ là một số nguyên tố.

b) Nguyên lý Dirichlet trong các bài toán hình học

Ví dụ 7: Có $33$ điểm trong hình vuông $4 \times 4$. Chứng minh rằng có $3$ điểm tạo thành tam giác có diện tích không lớn hơn $\dfrac{1}{2}$.

Ví dụ 8: Cho một tập $S$ gồm $25$ điểm sao cho với ba điểm bất kì thuộc $S$ thì có $2$ điểm khoảng cách nhỏ hơn $1$. Chứng minh rằng tồn tại một hình tròn bán kính $1$ chứa ít nhất $13$ điểm thuộc $S$.

Ví dụ 9: Cho đa giác đều có $14$ đỉnh. Chứng minh rằng từ $6$ đỉnh bất kì có thể chọn được $4$ đỉnh tạo thành một hình thang cân.

2. Bài tập

Bài 1: Cho $100$ số tự nhiên. Chứng minh rằng tồn tại một số hoặc mộ số các số có tổng chia hết cho $100$.

Bài 2: Chứng minh rằng tồn tại số tự nhiên chỉ toàn các chữ số $1$ và chia hết cho $2017$.

Bài 3: Cho bảng ô vuông $5 \times 5$, người ta điền vào các ô vuông các số $-1,0,1$. Xét tổng các số ở các dòng, cột và đường chéo, chứng minh rằng trong các tổng này có hai tổng bằng nhau.

Bài 4: Cho $5$ số nguyên dương đôi một phân biệt sao cho trong các số ấy thì chỉ có ước nguyên tố là $2$ và $3$. Chứng minh rằng có hai số mà tích của chúng là một số chính phương.

Bài 5: Có $20$ số nguyên dương phân biệt không lớn hơn $70$. Xét tất cả các hiệu của $2$ số, chứng minh rằng trong các hiệu đó có $4$ số bằng nhau.

Bài 6: Xét $20$ số tự nhiên $1, 2, \dots, 20$. Hãy tìm số nguyên dương $k$ nhỏ nhất sao cho với mỗi cách lấy $k$ số phân biệt từ $20$ số trên đều lấy được hai số $a, b$ sao cho $a + b$ là một số nguyên tố.

Bài 7:

a) Tô các cạnh của một lục giác bằng $2$ màu xanh đỏ. Chứng minh rằng tồn tại một tam giác được tô cùng một màu.

b) Tô các cạnh của một đa giác $17$ cạnh bằng $3$ màu. Chứng minh rằng tồn tại một tam giác được tô cùng một màu.

Bài 8: Trên đường tròn cho $16$ điểm tô bởi một trong ba mày: Xanh, Đỏ, Vàng. Các dây cung nối $2$ điểm trong $16$ điểm trên được tô bởi hai màu trắng, đen. Chứng minh ta luôn có $3$ điểm trong $16$ điểm trên tô cùng màu và $3$ cạnh của nó cũng được tô cùng màu.

Bài 9: Chứng minh rằng trong $52$ số tự nhiên bất kì luôn tìm được $2$ số mà tổng hoặc hiệu của chúng chia hết cho $100$.

Bài 10: Từ các số $1, 2, …, 2n$ lấy ra $n+1$ số. Chứng minh rằng:

a) Có $2$ số nguyên tố cùng nhau.

b) Có $2$ số mà số này chia hết cho số kia.

Bài 11: Có $81$ số gồm $9$ chữ số $1, 9$ chữ số $2, \dots, 9$ chữ số $9$. Xếp $81$ số này thành một dãy, có tồn tại hay không một cách xếp sao cho giữa hai chữ số $k$ có đúng $k$ số với $k = 1, 2, \dots, 9$.

Bài 12: Có $51$ điểm trong một hình vuông có cạnh bằng $1$. Chứng minh rằng tồn tại $3$ điểm có thể chứa trong một hình tròn bán kính $\dfrac{1}{7}$.

Bài 13: Cho đa giá có $2018$ cạnh, chứng minh rằng có một đường chéo không song song với bất kì cạnh nào.

Bài 14: Mỗi đỉnh của một đa giác đều $7$ cạnh được tô màu đỏ hoặc xanh. Chứng minh rằng có $3$ đỉnh tạo thành một tam giác cân và được tô cùng một màu.

Bài 15: Có $9$ đường thẳng trong đó mỗi đường thẳng chia hình vuông ra làm $2$ phần tỉ lệ diện tích là $2:3$. Chứng minh rằng có $3$ đường thẳng đồng quy.

Bài 16: (PTNK 2011) Cho hình chữ nhật $3 \times 4$.

a) Có $7$ điểm trong hình chữ nhật. Chứng minh có $2$ điểm khoảng cách không lớn hơn $\sqrt{5}$.

b) Có $6$ điểm trong hình chữ nhật. Chứng minh có $2$ điểm khoảng cách không lớn hơn $\sqrt{5}$.