Nguyên lí Dirichlet được cho là sử dụng lần đầu tiên vào năm 1834, bởi nhà toán học Johann Peter Gustav Lejeune Dirichlet. Nguyên lí này là một trong những công cụ mạnh nhất nhưng đơn giản nhất trong giải toán tổ hợp. Nguyên lí Dirichlet được ứng dụng trong lí thuyết đồ thị, tổ hợp số học và cả tổ hợp hình học. Thậm chí nguyên lí Dirichlet còn có những ứng dụng sâu sắc trong những lĩnh vực khác của toán học như lí thuyết số và giải tích. Trong các kì thi Olympic, ta được phép sử dụng nguyên lí Dirichlet mà không cần chứng minh. Điều quan trọng nhất là tìm cách áp dụng nguyên lí này một cách chính xác và hợp lí nhất. Phát biểu nguyên lí Dirichlet: Nếu nhốt $n+1$ con thỏ vào $n$ cái lồng thì có một cái lồng chứa ít nhất hai con thỏ. Nếu nhốt $nm+1$ con thỏ vào $n$ cái lồng thì có một cái lồng chứa ít nhất $m+1$ con thỏ. $\boxed{\text{Ví dụ 1}}$ Xét tập $M=\left\{1,2,\ldots,9\right\}.$ Với mỗi tập con $X$ của $M$, ta kí hiệu $S(X)$ là tổng các phần tử thuộc $X$. Chứng minh rằng trong số $26$ tập con $X$ của $M$ với $|X|\le 3$, luôn tồn tại hai tập $A$ và $B$ sao cho $S(A)=S(B)$. Spoiler: Lời giải Ta chia các tập con $X$ của $M$ thỏa mãn $|X|\le 3$ vào các lồng, mỗi lồng bao gồm các tập có cùng tổng các phần tử. Do $0\le S(x)\le 24$ nên có $25$ lồng. Do có $26$ tập $X$ với $|X|\le 3$ nên tồn tại hai tập $A,B$ thuộc cùng một lồng. Điều đó có nghĩa là tồn tạp hai tập $A,B$ sao cho $S(A)=S(B).$ $\boxed{\text{Ví dụ 2}}$ Cho tập $X=\left\{1,2,\ldots,2009\right\}.$ Chứng minh rằng trong số $1006$ phần tử bất kì của $X,$ luôn có hai phần tử có tổng bằng 2010. Spoiler: Lời giải Ta cần xác định thỏ và lồng trong bài toán này. Thỏ: Các phần tử của $X.$ Lồng: Tập hợp các cặp phần tử có tổng bằng $2010$ (chẳng hạn phần tử $1$ và $2009$ được nhốt chung trong một lồng). Có tổng cộng $1005$ lồng như vậy, bao gồm \begin{align*} (1,2009),(2,2008),\ldots,(1005,1005). \end{align*} Vì có $1005$ cặp và $1006$ phần tử nên tồn tại hai phần tử thuộc cùng một cặp, tức có tổng bằng $2010.$ $\boxed{\text{Ví dụ 3}}$ Cho tập hợp $X=\left\{1,2,3,\ldots,81\right\}.$ Chứng minh rằng trong $3$ phần tử tùy ý của $X$ luôn có hai phần tử $a,b$ sao cho \begin{align*} 0<\sqrt[4]{a}-\sqrt[4]{b}\le 1. \end{align*} Spoiler: Lời giải Xét $3$ phần tử $x_1,x_2,x_3$ của $X$. Đặt $c_i=\sqrt[4]{x_i}$. Khi đó \begin{align*} 1\le c_i\le 3,\text{ với mọi }i\in \left\{1,2,3\right\}. \end{align*} Chia khoảng $[1,3]$ thành $[1,2)$ và $[2,3]$. Theo nguyên lí Dirichlet, tồn tại hai trong ba số $c_1,c_2,c_3$ thuộc cùng một trong hai khoảng trên. Giả sử $x=\sqrt[4]{a}$ và $y=\sqrt[4]{b}$ là hai số đó thì $x$ và $y$ là hai số thỏa mãn yêu cầu đề bài. $\boxed{\text{Ví dụ 4}}$ Bên trong $\triangle ABC$ đều có cạnh bằng $6$, cho $13$ điểm phân biệt. Chứng minh rằng tồn tại hai trong số $13$ điểm đã cho có khoảng cách giữa chúng không vượt quá $\sqrt{3}.$ Spoiler: Lời giải Để áp dụng nguyên lí Dirichlet, ta cần chia tam giác thành 12 phần sao cho mỗi phần có đường kính không vượt quá $\sqrt{3}.$ Dưới đây là một cách chia thỏa mãn. Để xây dựng được cách chia này, ý tưởng là ta sẽ phủ $\triangle ABC$ bởi các hình có đường kính là $\sqrt{3}.$ Các hình được dùng để phủ phải đảm bảo có diện tích càng lớn càng tốt. Do đó đầu tiên, ta sẽ phủ bằng hình tròn, sau đó chỉnh sửa (chia lại thành các đa giác) để được thu được hình cuối cùng. Dễ nhận thấy trong cách chia này, ta chỉ cần 10 hình tròn để phủ cả tam giác. Từ đó ta thu được một kết quả tối ưu hơn so với đề bài (11 điểm thay vì 13 điểm). $\boxed{\text{Ví dụ 5}}$ Trên mặt phẳng có $6$ điểm, trong đó không có $3$ điểm nào thẳng hàng. Các điểm đã cho được nối với nhau bởi các đoạn thẳng xanh hoặc đỏ. Chứng minh rằng tồn tại $3$ điểm trong số $6$ điểm đó sao cho tam giác được tạo thành từ $3$ điểm đó cùng màu. Spoiler: Lời giải Lấy điểm $A$ là một trong $6$ điểm đã cho. Xét $5$ đoạn thẳng nối từ $5$ điểm còn lại tới $A.$ Theo nguyên lí Dirichlet, tồn tại $3$ đoạn thẳng trong số chúng cùng màu. Giả sử đó là $AB,AC,AD$ (màu xanh). Ta xét hai trường hợp. Tồn tại một trong $3$ đoạn thẳng $BC,BD,CD$ có màu xanh. Giả sử đoạn thẳng đó là $BC$. Khi đó ba điểm $A,B,C$ là ba điểm thỏa mãn đề bài (tạo thành tam giác có ba cạnh màu xanh). Cả ba đoạn thẳng $BC,BD,CD$ có màu đỏ. Khi đó ba điểm $B,C,D$ là ba điểm thỏa mãn đề bài (tạo thành tam giác có ba cạnh màu đỏ). $\boxed{\text{Ví dụ 6}}$ Cho tập hợp $A=\left\{1,2,\ldots,16\right\}.$ Hãy tìm số nguyên dương $k$ nhỏ nhất sao cho trong mỗi tập con gồm $k$ phần tử của $A$, tồn tại hai số phân biệt $a,b$ sao cho $a^2+b^2$ là số nguyên tố. Spoiler: Lời giải Với $k=8$, tập hợp $\left\{2,4,6,8,10,12,14,16\right\}$ là tập hợp có $8$ phần tử và tổng của hai phần tử bất kì đều là hợp số. Do đó $k\ge 9.$ Ta chứng minh $k=9$ là số thỏa mãn yêu cầu đề bài, tức với mọi tập con gồm $9$ phần tử của $A,$ tồn tại hai số phân biệt $a,b$ sao cho $a^2+b^2$ là số nguyên tố. Để chứng minh điều này, ta cần chia tập $A$ thành $8$ cặp số sao cho tổng bình phương của mỗi cặp là một số nguyên tố. Ta có cách chia như sau \begin{align*} (1,4),(2,3),(5,8),(6,11),(7,10),(9,16),(12,13),(14,15). \end{align*} Theo nguyên lí Dirichlet, trong $9$ phần tử bất kì của $A$, tồn tại hai phần tử thuộc cùng một cặp ở trên, tức có tổng bình phương là một số nguyên tố. $\boxed{\text{Ví dụ 7}}$ Chứng minh rằng trong $39$ số tự nhiên liên tiếp bất kì, tồn tại một số mà tổng các chữ số của nó chia hết cho $11.$ Spoiler: Lời giải Trong $20$ số đầu tiên có $2$ chữ số có tận cùng là $0.$ Một trong hai số đó có hàng chục khác $9$. Xét $11$ số \begin{align*} N,N+1,\ldots,N+9,N+19. \end{align*} Tổng các chữ số của các số này lần lượt là \begin{align*} s,s+1,\ldots,s+9,s+10. \end{align*} Trong $11$ số này sẽ có một số chia hết cho $11$. Bài toán được chứng minh. $\boxed{\text{Ví dụ 8}}$ Trong hình chữ nhật $3\times 4$ cho $6$ điểm. Chứng minh rằng tồn tại $2$ điểm trong số $6$ điểm đó có khoảng cách bé hơn hoặc bằng $\sqrt{5}.$ Spoiler: Lời giải Ta chia hình chữ nhật thành $5$ phần như sau. Theo nguyên lí Dirichlet, trong $6$ điểm bất kì thuộc hình chữ nhật, tồn tại $2$ điểm thuộc cùng một hình nhỏ, tức có khoảng cách bé hơn $\sqrt{5}.$ (Phần ý tưởng xây dựng các hình tròn đường kính $\sqrt{5}$ phủ hình chữ nhật $3\times 4$ xin dành lại cho bạn đọc).
$\boxed{\text{Bài toán 1}}$ Cho tập $X=\left\{1,2,3,\ldots,200\right\}$. Chứng minh rằng với mọi tập con $A$ của $X$ có số phần tử bằng $101$, luôn tồn tại hai phần tử mà phần tử này bằng bội của phần tử kia. Spoiler: Lời giải Giả sử $A=\left\{a_1,a_2,\ldots,a_{101}\right\}.$ Viết các số $a_i$ dưới dạng $a_i=2^{\alpha_i}b_i,$ trong đó $b_i$ là số lẻ. Xét các số lẻ $b_1,b_2,\ldots,b_{101}$. Ta có các số này đều thuộc $X$ mà trong $X$ chỉ có $100$ số lẻ nên tồn tại hai số $b_i=b_j$. Khi đó trong hai số $a_i$ và $a_j$, có một số là bội của số còn lại, bài toán được chứng minh. $\boxed{\text{Bài toán 2}}$ Có $65$ người đến từ hai quận, mỗi người làm một trong $4$ nghề. Biết rằng cứ $5$ người cùng nghề thì có hai người cùng tuổi. Chứng minh rằng có ít nhất $3$ người cùng tuổi, làm cùng một nghề và đến cùng một quận. Spoiler: Lời giải Giả sử không có ba người nào thỏa mãn bài toán. Theo nguyên lí Dirichlet, có ít nhất $33$ người đến cùng một quận. Trong số $33$ người này có ít nhất $9$ người làm cùng một nghề. Xét $5$ người nào đó trong số $9$ người trên, theo nguyên lí Dirichlet sẽ có hai người cùng tuổi là $A_1$ và $B_1$. Bỏ đi $A_1,B_1$ và xét $5$ người trong số $7$ người còn lại, ta có hai người cùng tuổi là $A_2,B_2$. Tiếp tục bỏ đi $A_2,B_2$ và xét $5$ người còn lại, ta có hai người cùng tuổi là $A_3,B_3$. Vì không có ba người nào thỏa mãn yêu cầu bài toán nên $A_1,A_2,A_3$ đôi một khác tuổi. Xét $A_1,A_2,A_3$ và 2 người trong số những người còn lại, ta có hai người cùng tuổi. Vì $A_1,A_2,A_3$ đôi một khác tuổi nên hai người cùng tuổi là $A_4,B_4$. Xét $5$ người gồm $A_1,A_2,A_3,A_4$ và nguồi còn lại cuối cùng, ta có hai người cùng tuổi. Điều này là vô lí, tức giả sử ban đầu sai, bài toán được chứng minh. $\boxed{\text{Bài toán 3}}$ Cho $n>1$ và $n+2$ số nguyên dương $$1\le a_1<a_2<\ldots<a_{n+2}\le 3n.$$ Chứng minh rằng tồn tại hai số $a_i$ và $a_j$ sao cho $n<a_i-a_j<2n.$ Spoiler: Lời giải Bằng cách tịnh tiến đều các điểm $a_i$, ta có thể giả sử $a_{n+2}=3n$. Nếu tồn tại $a_i$ thỏa $n<a_i<2n$ thì $n<a_{n+2}-a_i<2_n$. Nếu không tồn tại $i$ sao cho $n<a_i<2n$ thì xét các cặp $$(1,2n),(2,2n+1),\ldots,(n,3n-1)$$ ta suy ra có hai số cùng thuộc một cặp. Hai số này thỏa mãn yêu cầu bài toán. $\boxed{\text{Bài toán 4}}$ Cho tập hợp $M$ gồm $11$ số thực phân biệt từ trong khoảng $1$ đến $1000$. Chứng minh rằng tồn tại hai số $x\ne y$ sao cho $$0<x-y<1+3\sqrt[3]{xy}.$$ Spoiler: Lời giải Xét $A=x-y-1-3\sqrt[3]{xy}$. Ta có $$A=(\sqrt[3]{x}-\sqrt[3]{y}-1)\left(\sqrt[3]{x^2}+\sqrt[3]{y^2}+1-\sqrt[3]{x}-\sqrt[3]{y}-\sqrt[3]{xy}\right).$$ Vì $\sqrt[3]{x}\in [1,10]$ với mọi $x\in M$ nên tồn tại $x,y$ sao cho $0<\sqrt[3]{x}-\sqrt[3]{y}<1$ (điều phải chứng minh). $\boxed{\text{Bài toán 5}}$ Cho $m$ là số nguyên dương. Chứng minh rằng tồn tại hai số nguyên $a,b$ thỏa mãn $|a|\le m,|b|\le m$ sao cho $$0<a+b\sqrt{2}\le \dfrac{1+\sqrt{2}}{m+2}.$$ Spoiler: Lời giải Xét $(m+1)^2$ số có dạng $x+y\sqrt{2}$ với $x,y \in \left\{0,1,2,\ldots,\right\}. $ Do $0\le x+y\sqrt{2}\le m(1+\sqrt{2})$ nên tồn tại hai số $c+d\sqrt{2}$ và $p+q\sqrt{2}$ sao cho $$\left|(c+d\sqrt{2})- (p+q\sqrt{2})\right|\le \dfrac{m(1+\sqrt{2})}{(m+1)^2-1}=\dfrac{1+\sqrt{2}}{m+2}.$$
$\boxed{\text{Bài toán 6}}$ Cho $\sum_{i=1}^n x^2_i=1$. Chứng minh rằng, với mọi số nguyên $k$ không nhỏ hơn $2,$ tồn tại bộ số nguyên $a_i$ không đồng thời bằng $0$ và $|a_i|\le k-1$ với mọi $i$ sao cho $$\left|\sum_{i=1}^n a_i,x_i\right|\le \dfrac{(k-1)\sqrt{n}}{k^n-1}$$ Spoiler: Lời giải Bằng cách thay $a_i$ bởi $-a_i$, ta có thể giả sử $x_i\ge 0$ với mọi $i.$ Khi đó $\sum_{i=1}^n x_i\le \sqrt{n(\sum x_i^2)}=\sqrt{n}.$ Xét tập $$B=\left\{x=\sum_{i=1}^nk_i x_i:k_i\in\mathbb{N},k_i\le k-1\right\}.$$ Ta có $0\le x\le (k-1)\sqrt{n},$ với mọi $x\in B$ và $|B|=k^n$. Suy ra tồn tại $x,x'$ sao cho $$0<|x-x'|<\dfrac{(k-1)\sqrt{n}}{k^n-1}.$$ Bài toán được chứng minh $\boxed{\text{Bài toán 7}}$ Cho $\alpha$ là một số vô tỉ. Chứng minh rằng tồn tại vô hạn các số nguyên $p,q$ với $q>0$ sao cho $$\left|\alpha- \dfrac{p}{q}\right|<\dfrac{1}{q^2}.$$ Spoiler: Lời giải Trước tiên, ta chứng minh với mọi số nguyên dương $N$, tồn tại các số nguyên dương $p,q$ với $1\le q\le N$ sao cho $$\left|\alpha-\dfrac{p}{q}\right|\le \dfrac{1}{qN}.$$ Thật vậy, chia khoảng $[0,1)$ thành $N$ khoảng $$B_k=\left[\dfrac{k-1}{N},\dfrac{k}{N}\right),k=1,2,\ldots,N.$$ Xét các số có dạng $\left\{q\alpha\right\},$ với $q=0,1,\ldots,N$. Theo nguyên lí Dirichlet, tồn tại hai số $\left\{q_1\alpha\right\},\left\{q_2\alpha\right\}\ (q_1>q_2)$ cùng thuộc khoảng $B_k$ nào đó. Khi đó ta có $$0<|\left\{q_1\alpha\right\}-\left\{q_2\alpha\right\}\|<\dfrac{1}{N}.$$ Suy ra $$\left|\alpha-\dfrac{[q_1\alpha]-[q_2\alpha]}{q_1-q_2}\right|<\dfrac{1}{N(q_1-q_2)}.$$ Từ đó ta có điều phải chứng minh. Trở lại bài toán giả sử có hữu hạn cặn số nguyên $(p,q)$ với $p>q$ thỏa mãn $$\left|\alpha-\dfrac{p}{q}\right|<\dfrac{1}{q^2}$$ và $X$ là tập tất cả các số như vậy. Khi đó với mọi số thực dương $M$ đủ nhỏ, ta có $$\left|\alpha-\dfrac{p}{q}\right|>M,\text{ với mọi }(p,q)\in X.$$ Chọn $N$ sao cho $N>q$ và $\dfrac{1}{M}<N.$ Khi đó tồn tại các số nguyên dương $p,q$ sao cho $$\left|\alpha-\dfrac{p}{q}\right|<\dfrac{1}{qN}.$$ Do $\dfrac{1}{qN}<\dfrac{1}{q^2}$ nên $(p,q)\in X$. Điều này không xảy ra vì $\dfrac{1}{qN}<M.$ $\boxed{\text{Bài toán 8}}$ Cho $n$ là số nguyên dương không chia hết cho $10$. Chứng minh rằng tồn tại số nguyên dương $a$ chia hết cho $n$ và trong biểu diễn thập phân của $a$ không chứa số $0$ nào. Spoiler: Lời giải Số $n$ không chia hết cho $10$ nên có một trong hai dạng $n=2^km$ với $(m,2)=(m,5)=1$ hoặc $n=5^km$ với $(m,2)=(m,5)=1.$ Đối với trường hợp đầu, tồn tại $A$ chia hết cho $2^k$ và trong biểu diễn thập phân của $A$ không chứa số $0$ nào. Bây giờ xét $m+1$ số $A,AA,\ldots, AA\ldots A$ ta suy ra tồn tại một chữ số chia hết cho $m$ và đó là số cần tìm. Trường hợp thứ hai được xét tương tự. $\boxed{\text{Bài toán 9}}$ Trên mặt phẳng tọa độ, một điểm $A(x,y)$ được gọi là điểm nguyên nếu $x,y\in\mathbb{Z}.$ Giả sử $A_1A_2A_3\ldots A_n$ là một $n-$giác lồi có tất cả các đỉnh là điểm nguyên. Biết rằng miền đa giác đó (bao gồm tất cả các điểm thuộc miền trong và biên) không chứa bất cứ một điểm nguyên nào ngoại trừ các đỉnh của $n-$giác. Chứng minh rằng $n\le 4.$ Spoiler: Lời giải Vì các đỉnh của đa giác là các điểm nguyên nên tọa độ $(x,y)$ của mỗi đỉnh thuộc một trong $4$ dạng: (chẵn, chẵn), (chẵn, lẻ), (lẻ, chẵn), (lẻ, lẻ). Giả sử $n\ge 5.$ Khi đó tồn tại hai đỉnh mà tọa độ của chúng thuộc cùng một dạng. Giả sử hai đỉnh đó là $A(x_1,y_1),B(x_2,y_2).$ Khi đó trung điểm $M$ của $AB$ có tọa độ là $(x_M,y_M)$ thỏa $$x_M=\dfrac{x_1+x_2}{2}\in \mathbb{Z},\ y_M=\dfrac{y_1+y_2}{2}\in \mathbb{Z}.$$ Điều này trái với giả thiết nên $n\le 4.$ $\boxed{\text{Bài toán 10}}$ Có $15$ đại biểu của LTTK Education ngồi quanh bàn tròn sao cho không có vị nào ngồi đúng chỗ của mình như ban tổ chức đã sắp xếp (các vị trí được xếp cách đều nhau). Chứng minh rằng có thể xoay bàn để có ít nhất một đại biểu ngồi đúng chỗ của mình. Hãy chỉ ra một cách xếp sao cho có đúng một đại biểu ngồi đúng chỗ và mọi cách xoay bàn cũng chỉ có không quá 1 đại biểu ngồi đúng chỗ của mình. Spoiler: Lời giải Với mỗi đại biểu $A$, kí hiệu $d(A)$ là khoảng cách từ $A$ đến vị trị đúng của $A$ (khoảng cách trên đường tròn, tính theo chiều kim đồng hồ). Vì có $15$ đại biểu và chỉ có $14$ giá trị khoảng cách nên tồn tại hai đại biểu $A,B$ mà $d(A)=d(B).$ Khi quay bàn để $A$ đúng vị trí của $A$ thì $B$ cũng đúng vị trí của $B$. Bây giờ ta chỉ ta một cách sắp xếp sao cho có đúng một đại biểu ngồi đúng chỗ và mọi cách xoay bàn cũng chỉ có không quá một đại biểu ngồi đúng chỗ: Giả sử $15$ đại biểu là $A_1,A_2,A_3,\ldots,A_{15}$ và $A_i$ được xếp ngồi ở vị trí thứ $i$. Khi đó cách xếp sao cho $A_i$ ngồi ở vị trí mới $2i-1$ thỏa mãn yêu cầu bài toán.
$\boxed{\text{Bài toán 11}}$ Cho tập $M$ gồm $2002$ số nguyên dương, mỗi số chỉ có ước nguyên tố không vượt quá $23$. Chứng minh rằng tồn tại $4$ số phân biệt trong $M$ có tích là lũy thừa bậc $4$ của một số nguyên. Spoiler: Lời giải Có $9$ số nguyên tố không vượt quá $23$ là $$p_1=2,p_2=3,p_3=5,p_4=7,p_5=11,p_6=13,p_7=17,p_8=19,p_9=23.$$ Viết các số đã cho dưới dạng $$A=a^2.p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_9^{\alpha_9}$$ trong đó $a\in \mathbb{N}$ và $\alpha_i\in \left\{0,1\right\}.$ Do số bộ phân biệt $(x_1,x_2,\ldots,x_9)\in \left\{0,1\right\}^9$ là $2^9=512$ nên nếu xét $513$ phần tử thuộc $M$ thì theo nguyên tắc Dirichlet, tồn tại hai bộ $(\alpha_1,\ldots,\alpha_9)$ trùng nhau. Tương ứng hai bộ đó ta được hai số trong $M$ có tích là số chính phương. Giả sử hai số đó à $a_1,b_1$. Loại bỏ hai phần tử $a_1,b_1$ và xét $513$ phần tử của $M$ trong số còn lại, ta suy ra có hai phần tử $a_2,b_2$ có tích là số chính phương. Tiếp tục quá trình trên, ta nhận được $513$ cặp $(a_1,b_1),\ldots,(a_{513},b_{513})$ mà mỗi cặp có tích hai phần tử là một số chính phương. Bây giờ đặt $$a_1b_1=c_1^2,a_2b_2=c_2^2,\ldots,a_{513}b_{513}=c_{513}^2$$ và xét các số $c_i$. Vì các số này có ước nguyên tố không vượt quá $23$ nên suy ra có hai số $c_m,c_n$ có tích là số chính phương. Khi đó $4$ số $a_m,a_n,b_m,b_n$ có tích là lũy thừa bậc $4$ của số nguyên. $\boxed{\text{Bài toán 12}}$ Cho $A$ là tập $n$ số nguyên tố phân biệt và $M$ là tập gồm $n+1$ số tự nhiên phân biệt sao cho mỗi số trong $M$ đều không chính phương và chỉ có ước nguyên tố thuộc $A.$ Chứng minh có thể chọn ra trong $M$ một số có tích là một số chính phương. Spoiler: Lời giải Số tập con phân biệt khác rỗng của $M$ là $$C^1_{n+1}+\ldots+C_{n+1}^{n+1}-1=2^{n+1}-1.$$ Gọi các tập con đó là $M_1,M_2,\ldots,M_{2^{n+1}-1}$ và $a_i$ là tích các phần tử của $M_i$. Giả sử các phần tử của $A$ là $p_1<p_2<\ldots,<p_n$. Ta viết các số $a_i$ dưới dạng $a_i=b_i^2p_1^{\alpha_{i_1}}p_2^{\alpha_{i_2}}\ldots p_n^{\alpha_{i_n}}$ với $\alpha_{i_j}\in \left\{0,1\right\}.$ Ta có $2^{n+1}-1$ bộ $(\alpha_{i_1},\alpha_{i_2},\ldots,\alpha_{i_n})$ thuộc $\left\{0,1\right\}^n$, có $2^n$ phần tử. Do đó tồn tại $i\ne k$ thỏa $(\alpha_{i_1},\alpha_{i_2},\ldots,\alpha_{i_n})=(\alpha_{k_1},\alpha_{k_2},\ldots,\alpha_{k_n})$. Khi đó $a_ia_k$ là số chính phương. Bây giờ ta bỏ các phần tử thuộc giao của $M_i$ và $M_k$ ta còn lại các phần tử khác nhau mà tích là một số chính phương. $\boxed{\text{Bài toán 13}}$ Cho bảng ô vuông kích thước $2000 \times 2001$. Hãy tìm số nguyên dương $k$ lớn nhất sao cho ta có thể tô màu $k$ ô vuông con của bảng thỏa mãn hai ô vuông con nào được tô màu cũng ko có đỉnh chung. Spoiler: Lời giải Đánh số các hàng từ trái qua phải, các cột từ trên xuống dưới, ta chia bảng ô vuông như sau Dễ thấy rằng bảng ô vuông được chia thành $1000.1001$ miền phân biệt Giả sử có nhiều hơn $1000.1001$ ô vuông được tô màu. Theo nguyên lí Dirichlet, có ít nhất hai ô vuông được tô màu nằm trong cùng một miền, tức tồn tại hai ô vuông được tô màu có chung đỉnh, điều này trái với giả thiết. Ta suy ra $k\le 1000.1001.$ Ta chỉ ra cách tô thỏa $k=1000.1001$ như sau: Tô tất cả các ô có tọa độ $(2x-1,2y-1)$, với $x\le 1000,y\le 1001$. Dễ thấy cách tô trên thỏa đề và số ô được tô là $1000.1001$. Vậy, giá trị lớn nhất của $k$ là $1000.1001.$ $\boxed{\text{Bài toán 14}}$ Với mỗi số nguyên dương $n\ge 2,$ ta xét một bảng ô vuông $n\times n$. Mỗi ô vuông con được tô bởi màu đỏ hoặc màu xanh. Tìm số $n$ nhỏ nhất sao cho với mỗi cách tô ta luôn chọn được một hình chữ nhật kích thước $m\times k,m\ge 2,k\le n$ sao cho $4$ ô vuông con ở $4$ góc của hình chữ nhật này cùng màu. Spoiler: Lời giải Gọi một hình chữ nhật (HCN) thoả mãn đề bài là một HCN tốt. Với $n\in \left\{2,3,4\right\}$ thì tồn tại một cách tô sao cho không tồn tại HCN tốt. Ta chứng minh với mọi $n\in\mathbb{N},n\ge 5$, hình vuông $n\times n$ luôn tồn tại một hình chữ nhật tốt. Với $n=5$, theo nguyên lí Dirichlet, trong mỗi cột của hình vuông $5\times 5$ luôn tồn tại $3$ ô cùng màu. Nếu tồn tại một cột có 5 ô đỏ (xanh), dễ thấy luôn tồn tại một HCN tốt với 4đỉnh màu xanh (đỏ). Nếu tồn tại một cột có 4 ô đỏ hoặc xanh. Giả sử cột đó có 4 ô đỏ: Ta thấy rằng trong 4 cột còn lại nếu có nhiều hơn một cột có 2 ô đỏ thì sẽ tồn tại một HCN tốt với 4 đỉnh màu đỏ. Do đó trong 4 cột còn lại chỉ có nhiều nhất một cột có 2 ô đỏ. Tức là ta sẽ có 3 cột có ít nhất 4 ô xanh, do đó tồn tại một HCN tốt với 4đỉnh màu xanh. Xét trường hợp tất cả các cột được tô 3 ô đỏ, 2 ô xanh hoặc 3 ô xanh, 2 ô đỏ: Theo nguyên lí Dirichlet, có ít nhất 3 cột có 3 ô được tô cùng màu, không mất tính tổng quát giả sử các ô này được tô cùng màu đỏ. Xét 4 hàng bất kì trong 5 hàng. Do hàng còn lại có tối đa 3 ô đỏ nên tổng số ô đỏ của 3 cột ở 4 hàng này không nhỏ hơn: $3.3 - 3 = 6 = 4 + 2$. Do đó theo nguyên lí Dirichlet, tồn tại 2 cột có cùng ô đỏ ở 2 trong 4 hàng này nêntồn tại một HCN tốt với 4 đỉnh màu đỏ. Vậy, luôn tồn tại một HCN tốt trong hình vuông $5\times 5$. Với $n>5$, hình vuông $n\times n$ chứa hình vuông $5\times 5$ nên luôn tồn tại một HCN tốt. Vậy $5$ là giá trị cần tìm. $\boxed{\text{Bài toán 15}}$ Cho $A$ và $B$ là hai tập con của tập $\left\{1,2,\ldots,100\right\}$ thỏa $|A|=|B|$ và $A\cap B=\emptyset.$ Xác định số phần tử lớn nhất của tập $A\cup B$ sao cho với mọi $n\in A,$ ta luôn có $2n+2\in B$. Spoiler: Lời giải Vì $2n+2\in B$ mà $B\subset \left\{1,2,\ldots,100\right\}$ nên $2n+2\le 100\Rightarrow n\le 49.$ Do đó $$A\subset \left\{1,2,\ldots,49\right\}.$$ Ta chia tập $\left\{1,2,\ldots,49\right\}$ thành $33$ tập con như sau. $16$ tập hai phần tử có dạng $\left\{k,2k+2\right\}$: $$\left\{1, 4\right\}, \left\{2, 6\right\}, \left\{3, 8\right\}, \left\{5, 12\right\}, \left\{7, 16\right\},\left\{9, 20\right\}, \\ \left\{10, 22\right\}, \left\{11, 24\right\}, \left\{13, 28\right\}, \left\{14, 30\right\}, \left\{15, 32\right\}, \left\{17, 36\right\}, \left\{18, 38\right\}, \left\{19, 40\right\},\left\{21, 44\right\}, \left\{23, 48\right\}.$$ $17$ tập một phần tử: $$\left\{25\right\}, \left\{26\right\}, \left\{27\right\}, \left\{29\right\}, \left\{31\right\}, \left\{33\right\},\left\{34\right\}, \\ \left\{35\right\}, \left\{37\right\}, \left\{39\right\}, \left\{41\right\},\left\{42\right\}, \left\{43\right\}, \left\{45\right\}, \left\{46\right\}, \left\{47\right\}, \left\{49\right\}.$$ Nếu $|A|\ge 34,$ theo nguyên lí Dirichlet tồn tại ít nhất một trong 16 tập con ở nhóm một có 2 phần tử đều thuộc tập $A$, tức tồn tại hai số $x$ và $2x+2$ thuộc cùng tập $A$. Điều này là trái với giả thiết. Do đó $|A|\le 33.$ Khi đó $|A\cup B|=|A|+|B|-|A\cap B|=2|A|\le 66.$ Ta chọn hai tập $A,B$ như sau $$A=\left\{1, 2, 3, 5, 7, 9, 10, 11, 13, 14, 15, 17, 18, 19, 21, 23, 25, 26, 27, 29, 31, 33, 34, 35, 37, 39, 41, 42, 43, 45, 46, 47, 49 \right\}$$ và $$B=\left\{2k+2,k\in A\right\}.$$ Khi đó $A,B$ thỏa đề và $|A\cup B|=66$. Vậy số phần tử lớn nhất của $A\cup B$ là $66$.
$\boxed{\text{Bài toán 16}}$ Cho tập $X=\left\{1,2,\ldots,15\right\}.$ Gọi $M$ là một tập con của $X$ thỏa mãn tích ba phần tử bất kì của $M$ đều không phải số chính phương. Hỏi $M$ có tối đa bao nhiêu phần tử? Spoiler: Lời giải Gọi bộ ba phần tử bất kì của $X$ với tích là một số chính phương là một bộ xấu. Ta chia tập $X$ thành $5$ tập như sau: $$A_1=\left\{1,4,9\right\},A_2=\left\{2,6,12\right\},A_3=\left\{3,5,15\right\},A_4=\left\{7,8,14\right\},B=\left\{10,11,13\right\}.$$ Ta thấy rằng bộ ba phần tử $A_i,i=1,2,3,4$ là các bộ xấu. Nếu $|M|\ge 12$ thì theo nguyên lí Dirichlet, có ít nhất $2$ trong $5$ tập trên là con của $M$, suy ra có ít nhất một bộ xấu chứa trong $M$. Như vậy $|M|\le 11.$ Nếu $M=11$ thì theo nguyên lí Dirichlet, có $1$ trong $5$ tập trên là tập con của $M$. Để $M$ không chứa bộ xấu thì tập $B$ phải là tập con của $M$, các tập $A_i,i=1,2,3,4$ đều có $2$ phần tử thuộc $M$. Vì $B\subset M$ nên $10\in M$. Ta có hai bộ xấu đi với $10$ là $\left\{2,5,10\right\}$ và $\left\{6,10,15\right\}.$ Dễ thấy rằng thấy rằng nếu cả $3$ và $12$ không thuộc $M$ thì sẽ có ít nhất một trong hai bộ xấu trên được chứa trong $M$. Suy ra $3\in M$ và $12\in M$. Tuy nhiên ta lại có hai bộ xấu đi với $3$ và $12$ là hai bộ $\left\{3, 12, 1\right\}, \left\{3, 12, 9\right\}$. Mặt khác $1$ và $9$ đều thuộc tập $A_1$ nên chắc chắn có ít nhất một trong hai phần tử này thuộc $M$. Điều này đồng nghĩa với việc một trong hai bộ xấu trên sẽ chứa trong $M$, mâu thuẫn với giả thiết. Vậy $|M|\le 10.$ Tập $M$ có $10$ phần tử thỏa yêu cầu là $$\left\{1,4, 5, 6, 7, 10, 11, 12, 13, 14\right\}.$$ Vậy số phần tử lớn nhất của $M$ là $10$. $\boxed{\text{Bài toán 17}}$ Cho $n+1$ số nguyên dương khác nhau nhỏ hơn $2n$. Chứng minh rằng tồn tại ba số trong $n+1$ số đó mà một số bằng tổng của hai số còn lại. Spoiler: Lời giải Gọi $n+1$ số nguyên dương đã cho là $a_1,a_2,\ldots, a_{n+1}.$ Không mất tính tổng quát, ta gia sử $$1\le a_1<a_2<\ldots<a_{n+1}\le 2n-1.$$ Đặt $b_i=a_i-a_1,i=2\ldots n+1.$ Khi đó $$1\le b_2<b_3<\ldots<b_{n+1}\le 2n-1.$$Xét dãy $2n$ số nguyên $a_i,b_i,i=2\ldots n+1$. Các số này nhận $2n-1$ giá trị khác nhau nên theo nguyên lí Dirichlet, có ít nhất $2$ số trong chúng bằng nhau. Mặt khác $a_i\ne a_j, b_i\ne b_j$ với mọi $i\ne j,2\le i,i<n+1$. Ngoài ra $a_i\ne b_i$ với mọi $i\ge 2.$ Suy ra tồn tại $a_x=a_y-a_1$ hay $a_1+a_x=a_y$. Vậy ta có điều cần chứng minh. $\boxed{\text{Bài toán 18}}$ Cho $2014$ số tự nhiên bất kì. Chứng minh rằng luôn tồn tại $729$ số có tổng chia hết cho $729$. Spoiler: Lời giải Ta chứng minh bổ đề sau: Trong $5$ số tự nhiên, luôn tồn tại $3$ số mà có tổng chia hết cho $3$. Thật vậy, giả sử $5$ số tự nhiên $a_i,i=1\ldots 5$ có số dư khi chia cho $5$ lần lượt là $b_i,i=1\ldots 5.$ Nếu các số $b_i$ chỉ nhận một giá trị thì ba số bất kì trong các số $a_i$ đều có tổng chia hết cho $3$. Nếu các số $b_i$ nhận hai giá trị thì theo nguyên lí Dirichlet, tồn tại ba số trong chúng nhận giá trị bằng nhau. Khi đó ba số $a_i$ tương ứng sẽ có tổng chia hết cho $3$. Nếu các số $b_i$ nhận ba giá trị thì tổng của ba số $a_i$ tương ứng với ba số $b_i$ có giá trị khác nhau sẽ chia hết cho $3.$ Ta chứng minh bổ đề tiếp theo: Trong $53$ số bất kì luôn tồn tại $27$ số có tổng chia hết cho $27$. Thật vậy, gọi tập $53$ số tự nhiên đó là $A$. Ta có $|A|=53=17.3+2$. Theo bổ đề đầu tiên, tồn tại $3$ số có tổng chia hết cho $3$, ta gọi tổng này là $B_1$. Bỏ đi $3$ số này, áp dụng bổ đề đầu tiên, ta tiếp tục suy ra tồn tại $3$ số có tổng chia hết cho $3$, gọi tổng này là $B_2$. Ta cứ tiếp tục như vậy cho đến khi được $17$ bộ $B_i$ (vì $53=17.3+1$). Vì $17=5.3+2$ nên tồn tại $5$ số $C_j,j=1\ldots 5$ sao cho mỗi số là tổng của $3$ số $B_i$ và chia hết cho $3$. Mặt khác các số $B_i$ này chia hết cho $3$ nên suy ra các số $C_j$ chia hết cho $9$. Xét $5$ số $C_j$ ở trên, áp dụng bổ đề đầu tiên, ta suy ra tồn tại số $D$ sao cho $D$ là tổng của 3 số $C_j$ và chia hết cho $3.$ Mặt khác các số $C_j$ này chia hết cho $9$ nên suy ra $D\equiv 27.$ Ngoài ra $D$ còn là tổng của $3.3.3=27$ phần tử của $A$. Bổ đề được chứng minh. Trở lại bài toán, gọi tập $1457$ số tự nhiên đã cho là $X$. Áp dụng bổ đề thứ hai, chứng minh tương tự như trên, ta suy ra tồn tại số $S$ chia hết cho $27.27=729$ và $S$ là tổng của $27.27=729$ phần tử của $X$. Bài toán được chứng minh. $\boxed{\text{Bài toán 19}}$ Chứng minh rằng với $13$ điểm nguyên (hoành độ và tung độ là các số nguyên) bất kì trong mặt phẳng, tồn tại ba điểm sao cho trọng tâm của tam giác tạo bởi ba điểm đó có tọa độ nguyên. Spoiler: Lời giải Cho $5$ số nguyên bất kì, theo $\text{Bài toán 18}$, tồn tại $3$ trong số chúng có tổng chia hết cho $3$. Với $13$ điểm có tọa độ nguyên bất kì, tồn tại $5$ điểm trong số chúng sao cho hoành độ có cùng số dư khi chia cho $3$. Trong $5$ điểm này, tồn tại $3$ điểm sao cho tổng tung độ của chúng chia hết cho $3$. Khi đó trọng tâm của tam giác tạo bởi $3$ điểm này có tọa độ nguyên. $\boxed{\text{Bài toán 20}}$ Chứng minh rằng trong một bữa tiệc, luôn tồn tại hai người có số cái bắt tay bằng nhau. Spoiler: Lời giải Gọi $n$ là số người trong bữa tiệc. Số cái bắt tay của mỗi người là một số nguyên trong đoạn từ $0$ đến $n-1$. Nếu tồn tại một người không bắt tay với ai thì sẽ không tồn tại người nào có $n-1$ cái bắt tay và ngược lại, nếu tồn tại một người có $n-1$ cái bắt tay thì không tồn tại người nào không bắt tay với ai. Khi đó số cái bắt tay của mỗi người trong bữa tiệc đó chỉ nhận một trong $n-1$ giá trị ($0$ đến $n-2$ hoặc $1$ đến $n-1$). Vì có $n$ người nên tồn tại hai người có số cái bắt tay bằng nhau.
Số RamseyTheo $\textbf{Ví dụ 5}$, cho trước $6$ điểm trong mặt phẳng sao cho đoạn thẳng nối hai điểm bất kì trong chúng được tô bởi một trong hai màu thì tồn tại một tam giác có ba cạnh cùng màu với đỉnh là $3$ điểm trong số $6$ điểm đã cho. Câu hỏi được đặt ra là có thể mở rộng tính chất này cho số điểm lớn hơn hay không. Điều này có nghĩa là, cho trước hai số tự nhiên $l$ và $s$, liệu có tồn tại số $n\ge \max\left\{l,s\right\}$ sao cho với $n$ điểm bất kì trong mặt phẳng sao cho hai điểm bất kì giữa chúng được nối bởi đoạn thẳng màu xanh hoặc màu đỏ thì luôn tồn tại $l$ điểm sao cho các đoạn thẳng nối giữa $2$ điểm trong $l$ điểm đó đều màu xanh hoặc $s$ điểm sao cho các đoạn thẳng nối giữa $2$ điểm trong $s$ điểm đó đều màu đỏ. $\textbf{Ví dụ 5}$ ứng với $l=s=3$ và $n=6$. Trong trường hợp $n$ là số nhỏ nhất thỏa mãn điều trên, ta gọi $n$ là số Ramsey của cặp $(l,s)$ và kí hiệu là $n=r(l,s).$ $\boxed{\text{Ví dụ 9}}$ Chứng minh rằng $r(3,3)=6$. Spoiler: Lời giải Theo $\textbf{Ví dụ 5}$, ta chứng minh được rằng với $6$ điểm trong mặt phẳng sao cho đoạn thẳng nối hai điểm bất kì trong chúng được tô bởi một trong hai màu thì tồn tại một tam giác có ba cạnh cùng màu với đỉnh là $3$ điểm trong số $6$ điểm ấy, tức $r(3,3)\ge 6$. Ta chứng minh $r(3,3)=6$ bằng cách chỉ ra $5$ điểm sao cho hai điểm bất kì trong chúng được nối bởi đoạn thẳng màu xanh hoặc màu đỏ và không tồn tại $3$ điểm trong số đó sao cho tam giác được tạo thành có ba cạnh cùng màu. $\boxed{\text{Ví dụ 10}}$ Cho $l$ là số nguyên dương. Chứng minh rằng $r(2,l)$ tồn tại và $r(2,l)=l$. Spoiler: Lời giải Cho $l$ điểm bất kì trong mặt phẳng sao cho hai điểm bất kì giữa chúng được nối bởi các đoạn thẳng màu xanh hoặc màu đỏ. Nếu không tồn tại hai điểm được nối bởi đoạn thẳng màu xanh thì tất cả các đoạn thẳng đều màu đỏ. Vậy $r(2,l)= l.$ $\boxed{\text{Ví dụ 11}}$ Với mỗi cặp số nguyên $(l,s),l,s\ge 2$ mà $r(l,s)$ tồn tại thì $r(l,s)\le r(l-1,s)+r(l,s-1)$. $\boxed{\text{Ví dụ 12}}$
