Quay lại giao diện cũ
Nguyên lí Dirichlet (Nâng cao)
Cho $X$ là một tập hợp gồm $700$ số nguyên dương đôi một khác nhau, mỗi số không vượt quá $2$ $006$. Chứng minh rằng 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
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\}$.
Cho tập hợp $X = \{1; \, \sqrt2; \, \sqrt3; \, ...; \, \sqrt{2024}\}$. Chứng minh rằng 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
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$.
Cho $A$ là tập hợp gồm $6$ phần tử bất kỳ của tập hợp $\{0; \, 1; \, 2; \, ...; \, 14\}$. Chứng minh rằng tồn tại hai tập hợp con $B_1$ và $B_2$ của tập hợp $A$ (với $B_1$, $B_2$ khác nhau và khác rỗng) sao cho tổng tất cả các phần tử của tập hợp $B_1$ bằng tổng tất cả các phần tử của tập hợp $B_2$.
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.
Cho tập $A = \{1; \, 2; \, 3; \, ...; \, 16\}$. 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$ đều tồn tại hai số phân biệt $a$, $b$ mà $a^2 + b^2$ là một số nguyên tố.
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.
Trong một hình vuông diện tích là $16$, người ta đặt ba đa giác có tổng diện tích là $20$. Chứng minh rằng có hai đa giác có diện tích phần chung lớn hơn $1$.
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.