Câu hỏi 11
Cho dãy hữu hạn các số thực $A_{0}=\left(a_{1}, \ldots, a_{n}\right)$. Với mỗi $k \geq 0$, từ dãy $A_{k}=\left(x_{1}, \ldots, x_{n}\right)$, xây dựng dãy mới $A_{k+1}$ như sau.
1. Chọn phân hoạch $\{1, \ldots, n\}=I \cup J$, trong đó $I$, $J$ rời nhau, sao cho
$$
\left|\sum_{i \in I} x_{i}-\sum_{j \in J} x_{j}\right|
$$
đạt giá trị nhỏ nhất có thể. Cho phép $I$ hoặc $J$ rỗng; tổng tương ứng khi đó bằng 0. Nếu có nhiều phân hoạch như vậy, chọn tùy ý một phân hoạch.
2. Đặt $A_{k+1}=\left(y_{1}, \ldots, y_{n}\right)$, trong đó $y_{i}=x_{i}+1$ nếu $i \in I$, và $y_{i}=x_{i}-1$ nếu $i \in J$.
Chứng minh với một giá trị $k$, dãy $A_{k}$ chứa phần tử $x$ thỏa mãn $|x| \geq n / 2$.
1. Chọn phân hoạch $\{1, \ldots, n\}=I \cup J$, trong đó $I$, $J$ rời nhau, sao cho
$$
\left|\sum_{i \in I} x_{i}-\sum_{j \in J} x_{j}\right|
$$
đạt giá trị nhỏ nhất có thể. Cho phép $I$ hoặc $J$ rỗng; tổng tương ứng khi đó bằng 0. Nếu có nhiều phân hoạch như vậy, chọn tùy ý một phân hoạch.
2. Đặt $A_{k+1}=\left(y_{1}, \ldots, y_{n}\right)$, trong đó $y_{i}=x_{i}+1$ nếu $i \in I$, và $y_{i}=x_{i}-1$ nếu $i \in J$.
Chứng minh với một giá trị $k$, dãy $A_{k}$ chứa phần tử $x$ thỏa mãn $|x| \geq n / 2$.