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