Nguyên lí Dirichlet (Nâng cao) SVIP

Hướng dẫn giải:

Theo nguyên lí Dirichlet thì trong $700$ số có ít nhất $\left[\dfrac{700}3\right]+1 = 234$ số có cùng số dư khi chia cho $3$.

Gọi $234$ số đó là $1 \le a_1 < a_2 < ... < a_{234} \le 2$ $006$.

Giả sử không tồn tại hai số $a_i; \, a_j$ nào thỏa mãn $a_i - a_j \in E$ với $i, \, j = \overline{1, 234}$

Do đó $a_i - a_j \ge 12$ (vì $(a_i - a_j)$ $\vdots$ $3$ và $a_i \ne a_j$).

Trong $234$ số trên, hai số kề nhau hơn kém nhau ít nhất $12$ đơn vị nên $a_{234} - a_1 \ge 233.12 = 2$ $796 > 2$ $006$ (vô lí).

Như vậy trong tập hợp $X$ luôn tìm được hai phần tử $x$, $y$ sao cho $x - y$ thuộc tập hợp $E = \{3; \, 6; \, 9\}$.

Hướng dẫn giải:

Chia $2012$ số $1$; $\sqrt2$; $\sqrt3$; ... ; $\sqrt{2024}$ thành $44$ đoạn gồm $[\sqrt1; \, \sqrt3]$; $[\sqrt4; \, \sqrt8]$; ...; $[\sqrt{1936}; \, \sqrt{2012}]$.

 Các đoạn trên có dạng tổng quát là $\left[\sqrt{k^2}; \, \sqrt{(k+1)^2 - 1}\right]$ với $k \ge 1$.

Như vậy $90$ số thuộc tập hợp $X$ nằm trong $44$ đoạn trên. Theo nguyên lí Dirichlet thì tồn tại ba số trong $90$ số trên nằm trong cùng một đoạn.

Không mất tính tổng quát, ta giả sử hai số đó là $x$, $y$, $z$ và chúng nằm trong đoạn $\left[\sqrt{k^2}; \, \sqrt{(k+1)^2 - 1}\right]$.

Chia đoạn $\left[\sqrt{k^2}; \, \sqrt{(k+1)^2 - 1}\right]$ thành hai đoạn $\left[\sqrt{k^2}; \, \sqrt{(k^2 + k}\right]$ và $\left[\sqrt{k^2 + k}; \, \sqrt{(k+1)^2 - 1}\right]$. Khi đó theo nguyên lí Dirichlet tồn tại hai số nằm trên cùng một đoạn. Giả sử hai số đó là $x$, $y$. Khi đó:

 Nếu $x$ và $y$ nằm trên đoạn $\left[\sqrt{k^2}; \, \sqrt{(k^2 + k}\right]$ thì ta được

$|x - y| \le \sqrt{k^2 + k} - \sqrt{k^2} < \sqrt{k^2 + k +\dfrac14} - \sqrt{k^2} = k + \dfrac12 - k = \dfrac12.$

 Nếu $x$ và $y$ nằm trên đoạn $\left[\sqrt{k^2 + k}; \, \sqrt{(k+1)^2 - 1}\right]$ thì ta được:

$|x - y| \le \sqrt{(k+1)^2 - 1} - \sqrt{k^2 + k} = \dfrac{(k+1)^2 - 1 - k^2 - k}{\sqrt{(k+1)^2 - 1}+\sqrt{k^2 + k}} < \dfrac k{2k} = \dfrac12.$

Vậy trong $90$ số khác nhau bất kì được lấy ra từ tập $X$ luôn tồn tại hai số $x$, $y$ sao cho $|x - y| < \dfrac12$.

Hướng dẫn giải:

Do $A$ là tập hợp có $6$ phần tử nên số tập hợp con khác rỗng và khác $A$ của tập hợp $A$ là: $2^6 - 2 = 62$ (tập hợp con).

Xét tập hợp $X$ là tập con bất kì trong $62$ tập hợp con trên và $T(X)$ là tổng các phần tử của $X$.

Tập hợp $X$ có nhiều nhất $5$ phần tử thuộc tập hợp $\{0; \, 1; \, 2; \, ...; \, 14\}$ nên ta có:

$0 \le T(X) \le 10 + 11 + 12 + 13 + 14 = 60$.

Như vậy với $62$ tập hợp con của $A$ như trên thì tồn tại $62$ tổng không vượt quá $60$.

Theo nguyên lí Dirichlet thì tồn tại hai tổng có giá trị bằng nhau. Điều đó chứng tỏ tồn tại hai tập hợp con $B_1$, $B_ 2$ của tập hợp $A$ có tổng các phần tử của chúng bằng nhau.

Hướng dẫn giải:

Nếu $a$, $b$ chẵn thì $a^2 + b^2$ là hợp số. Do đó nếu tập con $X$ của $A$ có hai phần tử phân biệt $a$, $b$ mà $a^2 + b^2$ là một số nguyên tố thì $X$ không thể chỉ chứa các số chẵn.

Suy ra $k = 9$.

Ta chứng tỏ $k=9$ là giá trị nhỏ nhất cần tìm. Điều đó có nghĩa là với mọi tập con $X$ gồm $9$ phần tử bất kì của $A$ luôn tồn tại hai phần tử phân biệt $a$, $b$ mà $a^2 + b^2$ là một số nguyên tố.

Để chứng minh khẳng định trên ta chia tập $A$ thành các cặp hai phần tử phân biệt $a$, $b$ mà $a^2 + b^2$ là một số nguyên tố, ta có tất cả $8$ cặp $\{1;4\}$, $\{2;3\}$, $\{5;8\}$, $\{6;11\}$, $\{7;10\}$, $\{9;16\}$, $\{12;13\}$, $\{14;15\}$. Theo nguyên lí Dirichlet thì $9$ phần tử của $X$ có hai phần tử cùng thuộc một cặp và ta có điều phải chứng minh.

Hướng dẫn giải:

Trong lời giải này ta quy ước diện tích của đa giác $X$ bất kì là $|X|$.

Gọi ba đa giác đó là $A$, $B$ và $C$.

Khi đó $|A| + |B| + |C| = 20$.

Ta có: $|A \cup B \cup C| = |A| + |B| + |C| − (|A \cap B| + |B \cap C| + |C \cap A|) + |A \cap B \cap C|$. (∗)

Do $A$, $B$ và $C$ nằm trong hình vuông diện tích $16$ nên $|A \cup B \cup C| \le 16$ và hiển nhiên $|A \cap B \cap C| \ge 0$, từ đó kết hợp với (∗) ta suy ra $16 \ge |A| + |B| + |C| − (|A \cap B| + |B \cap C| + |C \cap A|)$ hay $|A \cap B| + |B \cap C| + |C \cap A| \ge |A| + |B| + |C| - 16 = 4$.

Do đó một trong ba số $ |A \cap B|$, $|B \cap C|$ và $|C \cap A|$ sẽ có ít nhất một số không nhỏ hơn $\dfrac43$ hay số đó sẽ lớn hơn $1$, giả sử $|A \cap B| > 1$.

Vậy $A$ và $B$ là hai đa giác thỏa mãn bài toán. Ta có điều phải chứng minh.