Cho tập hợp $A=(1,2,..,3n)$ với $n$ nguyên dương .Chứng minh rằng có thể chia tập $A$ thành các tập con mỗi tập gồm $n$ số và chúng đôi một không có phần tử chung .Chứng minh rằng luôn tồn tại một số thuộc tập này bằng tổng của hai số thuộc hai tập còn lại.
Giả sử không tồn tại bộ ba số nào thoả mãn đk đề bài.
Xét phân hoạch của tập $A$ là $A_1$, $A_2$, $A_3$
Không mất tính tổng quát, giả sử $1 \in A_1$.
Gọi $k$ là số tự nhiên nhỏ nhất không thuộc $A_1$
Giả sử $k \in A_2$
Xét $x \in A_3$
$x-1\notin A_2$
Giả sử $x-1\in A_3$
Vì $k$ là số tự nhiên nhỏ nhất không thuộc $A_1$ nên $x-k-1>0$
Xét 2 bộ ba số $\left ( x-k,k,x \right )$ và $\left ( x-k,k-1,x-1 \right )$ ta suy ra $x-k \in A_3$
Xét 2 bộ ba số $\left ( x-k-1,k,x-1 \right )$ và $\left ( x-k,x-k-1,1 \right )$ suy ra $x-k-1 \in A_3$
Làm tương tự như vậy ta suy ra $x-ik, x-ik-1 \in A_3$. Mặt khác, một lúc nào đó sẽ tồn tại 1 trong các số trên bé hơn $k$, vô lí.
Suy ra $x-1 \in A_1$
Vậy với mọi $x \in A_3$ thì $x-1 \in A_1$. Suy ra $\left | A_1 \right |=n+1$, vô lí
Vậy giả thiết phản chứng sai
Suy ra đpcm