Phải lấy ít nhất bao nhiêu số tự nhiên để chắc chắn tồn tại hai số mà hiệu của chúng chia hết cho 13

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\} $.

Giải

Gọi $676$ số đó là $a_1, a_2, …, a_{676}$.

Xét $676 \times 3 = 2028$ gồm $676$ số $a_1, a_2, …, a_{676}$; [nhóm 1], $676$ số $a_1+3, a_2+3, …,a_{676} +3$ [nhóm 2], $676$ số $a_1+6, a_2+6,…,a_{676}+6$ [nhóm 3].

$2028$ số này là các số tự nhiên không vượt quá $2022$ nên theo nguyên lý Dirichlet tồn tại $2$ số bằng nhau. Mà hai số cùng một nhóm không thể bằng nhau nên xảy ra $3$ trường hợp: $a_i = a_j+3$, $a_i = a_j + 6$ hoặc $a_i+3 = a_j+6$, trong cả ba trường hợp ta đều có $|a_i-a_j| \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?

Giải

Nếu tập $S$ có $7$ phần tử trở lên thì sẽ có không ít hơn $21$ tổng. Mà các tổng hai số chỉ nhận các giá trị từ $3$ đến $17$ nên theo nguyên lý dirichlet thì sẽ có hai tổng bằng nhau.

Do đó số phần tử của $S$ không lớn hơn $6$.

Xét $S$ có $6$ phần tử, khi đó có đúng $15$ tổng nhận các giá trị $3, 14, \dots, 17$ nên mỗi tổng hai số nhận đúng một giá trị. Để có tổng bằng $3$, $17$ thì tồn tại $4$ số $1, 2$ và $8, 9$. Khi đó $1 + 9 = 2+8$ [vô lý]. Vậy tập không thể có $6$ phần tử.

Nếu tập có $5$ phần tử, ta thấy $S = \left\{ 1, 2, 5, 7, 9\right\} $ thỏa đề bài.

Vậy số phần tử lớn nhất của một tập con thỏa đề bài là $5$.

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

Giải

Xét $2019$ số gồm $1010$ số đã cho [nhóm 1] và $1009$ số $a_2-a_1, a_3-a_1, …, a_{1010} – a_1$ [nhóm 2] nhận giá trị nguyên từ $1$ đến $2017$, theo nguyên lý dirichlet thì có hai số bằng nhau, hơn nữa các số nhóm 1 khác nhau, các số nhóm 2 khác nhau nên một số thuộc nhóm 1 bằng một số thuộc nhóm 2, do đó tồn tại $i, k$ sao cho $a_k-a_1 = a_i$ hay $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$.

Giải

Theo nguyên lý đirichlet thì trong $11$ số có hai số có hiệu chia hết cho $10$, gọi $2$ số đó là $a, b$. Ta có $a = x^2, b = y^2$ và $a-b = [x-y][x+y]$ chia hết cho $10$ nên $x, y$ cùng tính chẵn lẻ, do đó $[x-y][x+y]$ chia hết cho $4$. Vậy $a-b$ chia hết cho $4$ và chia hết cho $10$ nên 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.

Giải

$5$ số có dạng $2^a\cdot 3^b$ với $a, b$ là các số tự nhiên.

Xét tính chẵn lẻ của các cặp số $[a;b]$ ta chỉ có $4$ trường hợp là [chẵn; chẵn], [chẵn;lẻ], [lẻ; chẵn] và [lẻ; lẻ].

Khi đó với $5$ cặp số thì theo nguyên lý dirichlet có $2$ cặp $[a_1;b_1]$ và $[a_2;b_2]$ sao cho $a_1, a_2$ cùng tính chẵn lẻ và $b_1, b_2$ cùng tính chẵn lẻ.

Khi đó $a_1+a_2, b_1+b_2$ là chẵn, suy ra $2^{a_1}3^{b_1}\cdot 2^{a_2}3^{b_2} = 2^{a_1+a_2}\cdot 3^{b_1+b_2}$ là 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ố.

Giải

Xét $10$ số chẵn thì tổng hai số bất kì đều là hợp số, do đó đó $ k \geq 11$.

Ta chứng minh $k= 11$.

Xét $10$ cặp số $[1;2], [3;20], [4;19], \dots, [11;12]$, mỗi cặp số có tổng là số nguyên tố, khi đó với $11$ số thì theo nguyên lý dirichlet có $2$ số cùng một cặp, khi đó tổng của chúng 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}$.

Giải

Chia hình vuông thành $16$ hình vuông như hình vẽ, khi đó theo nguyên lý dirichlet thì có $3$ điểm cùng thuộc một hình vuông $1 \times 1$.

Ta cần chứng minh tam giác có $3$ đỉnh nằm trong hoặc trên cạnh hình vuông $1$ thì diện tích không quá $\dfrac{1}{2}$.

Xét tam giác $EFG$, đường thẳng qua $E$ song song với cạnh hình vuông cắt $FG$ tại $I$.

Khi đó $S_{EFG} = S_{EFI} +S_{EGI} = \dfrac{1}{2}FM\cdot EI + \dfrac{1}{2}GK\cdot EI = \dfrac{EI}{2}[FM+GK] \leq \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$.

Giải

Xét $2$ điểm $A$ và $B$ sao cho $AB$ có độ dài lớn nhất. Khi đó xét $2$ hình tròn $[A;1], [B;1]$ nếu chứa hết $25$ điểm thì sẽ có $13$ điểm cùng thuộc một hình tròn, ta có điều cần chứng minh.

Nếu có $1$ điểm $C$ không thuộc $2$ hình tròn trên thì trong $3$ điểm $A, B, C$ không có $2$ điểm nào khoảng cách nhỏ hơn $1$ [vô lý].

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.

Giải

Do tính chất đối xứng của tứ giác đều nên với hai đỉnh bất kì thì độ dài nối hai đỉnh đó có thể nhận $1$ trong $7$ giá trị.

Với $6$ đỉnh ta có $15$ đoạn thẳng nhận bảy giá trị độ dài khác nhau, theo nguyên lý dirichlet thì có $3$ đoạn có đoạn thẳng bằng nhau.

TH1: Nếu $3$ đoạn bằng nhau đó cùng chung một đỉnh, ví dụ $AB= AC = AD$, suy ra $B, C, D$ thuộc đường tròn tâm A [vô lý].

TH2: Có $2$ đoạn bằng nhau không chung một đỉnh, giả sử $AB = CD$. Ta có $ABCD$ nội tiếp và $AB = CD$ nên $4$ đỉnh $A, B, C, D$ tạo thành hình thang cân. [điều cần chứng minh].

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}$.

Related