Chủ đề này có 2 trả lời

[halloffame]

Chia các số từ 1 đến 3n vào 3 nhóm, mỗi nhóm n số. Chứng minh có thể chọn ở mỗi nhóm 1 số sao cho trong 3 số được chọn có 1 số bằng tổng 2 số kia.

[Zaraki]

Bài này làm mình tốn rất nhiều thời gian để nghĩ ra lời giải. Sau đây là lời giải của mình, mong mọi người có thể kiểm chứng lời giải này hộ mình.

 

Lời giải. Giả sử rằng tồn tại một cách chia nhóm mà không có số nào trong mỗi nhóm bằng tổng của hai số lần lượt thuộc hai nhóm kia. Gọi các nhóm và các số trong nhóm lúc đó là các tập: $A= \{ a_1,a_2, \cdots, a_n \}, \; B= \{ b_1,b_2, \cdots , b_n \}, \; C= \{ c_1,c_2, \cdots , c_n \}$. Không mất tính tổng quát, giả sử $1 \in A$. Khi đó $b_i \pm 1 \in A \; \text{or} \; B$.

 

Bước 1. Chứng minh $2 \in A$.

Giả sử phản chứng rằng $2 \in C$.

 

Nếu trong $B$ tồn tại hai số $b_y,b_x \; (b_y<3n)$ thoả $b_y-b_x=1$. Khi đó $(b_y+1)-b_x=2$. Ta suy ra $b_y+1 \not\in A$ vì nếu $b_y+1 \in A$ mà $2 \in C, b_x \in B$ suy ra điều mâu thuẫn với điều giả sử ban đầu. Vậy $b_y+1 \in B$. Chứng minh tương tự $b_y+2, b_y+3 \in B, \cdots , 3n \in B$. Ta cũng có $b_y-1=b_x \in B$ nên $b_y-(b_x-1)=2$ suy ra $b_x-1=b_y-2 \in B$. Như vậy $b_y-1,b_y-2, \cdots, 1 \in B$. Do đó $|B|=3n$, mâu thuẫn.

 

Nếu trong $B$ không tồn tại hai số $b_y,b_x \; (b_y<3n)$ thoả $b_y-b_x=1$. Khi đó $b_i \pm 1 \in A \; (1 \le i \le n-1)$ suy ra $|A| \ge 2n-2$, mâu thuẫn.

 

Vậy $2 \in A$.

 

Bước 2. Chứng minh $3 \in A$.

Ta đã có $1,2 \in A$ nên $b_i \pm 1,b_i \pm 2 \in A \; \text{or} \; B$. Giả sử phản chứng rằng $3 \in C$.

 

Nếu trong $B$ tồn tại hai số $b_y,b_x \; (b_y<3n)$ thoả mãn $b_y-b_x=1$. Khi đó $b_x,b_x+1 \in B$ nên $b_x+3 \in B$ (vì $b_x+3=(b_x+1)+2$ nên $b_x+3 \not\in C$ và nếu $b_x+3 \in A$ mà $b_x \in B, 3 \in C$ sẽ suy ra ngay mâu thuẫn). Tương tự $b_x+4, b_x+6,b_x+7, \cdots , ... \in B$ và $b_x-2,b_x-3, \cdots \in B$. Từ đây ta dễ dàng dẫn đến là $b_x+3l, bx+3l+1 \in B$ với mọi $l \in \mathbb{Z}$ sao cho $bx+3l,bx+3l+1 \le 3n$. Nếu tồn tại số $k=b_x+3m+2 \in C$ thì khi đó do $b_x+3m+1 \in B$ và $1 \in A$ và $1+(b_x+3m+1)=b_x+3m+2$ nên ta suy ra ngay mâu thuẫn.

 

Nếu trong $B$ không tồn tại hai số $b_y,b_x$ như thế thì ta suy ra ngay $b_i \pm 1 \in A \; (1 \le i \le n-1)$ suy ra $|A| \ge 2n-2$, mâu thuẫn.

 

Như vậy $3 \in A$.

 

Bước 3. $1,2, \cdots , n-1 \in A$. Chứng minh $n \in A$.

Như vậy ta đã có $1,2, \cdots , n-1 \in A$ suy ra $b_i \pm 1, b_i \pm 2, \cdots, b_i \pm (n-1) \in A \; \text{or} \; B$. Giả sử phản chứng $n \in C$.

 

Nếu trong $B$ tồn tại hai số $b_y,b_x \; (b_y<3n)$ thoả mãn $b_y-b_x=1$. Khi đó $b_x,b_x+1 \in B$ nên $b_x+n \in B$ (vì $b_x+n=(b_x+1)+(n-1)$ nên $b_x+n \in A \; \text{or} \; B$ mà nếu $b_x+n \in A$, lại có $n \in C, b_x \in B$ thì suy ra ngay mâu thuẫn). Tương tự $b_x+n+1, \in B$. Cứ như thế ta suy ra $b_x+nk,b_x+nk+1 \in B$ với $k \in \mathbb{Z}$ thoả mãn $1 \le b_x+nk,b_x+nk+1 \le 3n$. Xét có một số $m= b_x+ny+r \in C \; (0 \le r \le n-1, r \ne 0,1)$. Ta có số $b_x+ny+1 \in B$ mà $(b_x+ny+1)+(r-1)=b_x+ny+r$ với $1 \le r \le n-2$ nên $r-1 \in A$. Từ đây suy ra mâu thuẫn.

 

Nếu trong $B$ không tồn tại hai số $b_y,b_x$ như thế. Khi đó $b_i \pm 1 \in A \; (1 \le i \le n-1)$ suy ra $|A| \ge 2n-2$, mâu thuẫn.

 

Như vậy $n \in A$.

 

Ta có được $A= \{ 1,2, \cdots , n \}$. Giả sử hai tập $B,C$ có dãy

$$\begin{array}{l} b_{x_1}-b_{y_1}= b_{x_2}-b_{y_2}= \cdots = b_{x_k}-b_{y_k}=1, \\ c_{m_1}-c_{p_1}= c_{m_2}-c_{p_2}= \cdots = c_{m_l}-c_{p_l}=1. \end{array}$$

Trong đó $b_{x_1}, c_{m_1}$ tương ứng là hai số lớn nhất trong hai dãy. Không mất tính tổng quát, giả sử $b_{x_1}<c_{m_1} \le 3n$. Khi đó luôn tồn tại một số $T \le 3n$ sao cho $T \not\in B$ và $T-b_{x_1}=1$. Hiển nhiên $T \not\in A, T \not\in B$ (do điều kiện lớn nhất của $b_{x_1}$) nên $T \in C$. Từ đây dẫn đến mâu thuẫn với điều kiện giả sử ban đầu.

 

Như vậy, điều giả sử phản chứng sai. Hay nói cách khác, luôn tồn tại một số trong 1 nhóm mà bằng tổng của hai số lần lượt thuộc hai nhóm còn lại. Bài toán được chứng minh. $\blacksquare$

[Zaraki]

Lục lọi lung tung trên mạng thì tìm thấy bài toán là India TST 2003. Có một lời giải khác được đưa lên bởi thành viên Sayan bên AoPS.