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

[Hieutran2000]

Phân hoạch tập $\left \{ 1,2,...n \right \}$ thành $k$ tập con ( có thể =$\varnothing$) sao cho: trong mỗi tập con không tồn tại 3 số mà có 1 số bằng tổng 2 số còn lại. Chứng minh: $max (n)\leq [k!e]-1$.

Bài viết đã được chỉnh sửa nội dung bởi Hieutran2000: 10-06-2017 - 22:20

[redfox]

Bổ đề: $\left \lceil \frac{\left \lfloor k!e \right \rfloor}{k} \right \rceil=\left \lfloor \left ( k-1 \right )!e \right \rfloor+1$ (có thể chứng minh nhờ công thức: $e=\sum_{k=1}^{\infty }\frac{1}{k!}$).

Ta định nghĩa: $A-B=\left \{ a-b|a\in A,b\in B,a>b \right \}$. Để ý rằng $A\subset C,B\subset D\Rightarrow A-B\subset C-D$.

Ta sẽ chứng minh nếu tập $N\subset \mathbb{Z}^+$ có tập con $M$ thỏa mãn $\left | M \right |\geq \left \lfloor k!e \right \rfloor,M-M\subset N$ thì không tồn tại cách phân hoạch thỏa mãn đề. Ta chứng minh bằng quy nạp theo $k$.

Với $k=1$, dễ dàng chứng minh bài toán đúng.

Giả sử $k-1$ đúng, xét phân hoạch $N$ thành $k$ tập hợp $A_1,A_2,...,A_k$. Theo Dirichlet, tồn tại $A_i$ sao cho $\left | A_i\cap M \right |\geq \left \lceil \frac{\left | M \right |}{k} \right \rceil\geq \left \lfloor \left ( k-1 \right )!e \right \rfloor+1$. Gọi $x$ là phần tử lớn nhất của $A_i\cap M$. Đặt $M'=\left \{ x \right \}-A_i\cap M$, ta có $\left | M' \right |\geq \left \lfloor \left ( k-1 \right )!e \right \rfloor$. Dễ thấy $M',M'-M'\subset A_i\cap M-A_i\cap M\subset M-M\subset N;M',M'-M'\subset A_i-A_i$

TH1: $M'\cap A_i\neq \varnothing$ hoặc $\left ( M'-M' \right )\cap A_i\neq \varnothing$, ta chọn được ba số trong $A_i$, một số bằng tổng hai số còn lại nên cách phân hoạch này không thỏa mãn.

TH2: $M',M'-M'\subset N'=N/A_i$, áp dụng bài toán với $k-1,N',M'$ với cách phân hoạch $N'$ thành $k-1$ tập hợp $A_1,A_2,...,A_k$ (trừ $A_i$), cách phân hoạch này không thỏa mãn với $N'$ nên cách phân hoạch $N$ thành $k$ tập hợp $A_1,A_2,...,A_k$ như trên cũng không thỏa mãn đề.

Áp dụng bài toán với $N=M=\left \{ 1,2,..,n \right \},n\geq \left \lfloor k!e \right \rfloor$ ta thấy không tồn tại cách phân hoạch thỏa mãn, vậy $n\leq \left \lfloor k!e \right \rfloor-1$.

(Q.E.D)

Bài viết đã được chỉnh sửa nội dung bởi redfox: 13-06-2017 - 14:26

[Donald Trump]

Đây là định lý Schur, bạn có thể tham khảo cuốn Lý thuyết số sơ cấp của các số ( chương XII ).