2007 IMO Shortlist C4

Let $A_{0}=\left(a_{1}, \ldots, a_{n}\right)$ be a finite sequence of real numbers. For each $k \geq 0$, from the sequence $A_{k}=\left(x_{1}, \ldots, x_{n}\right)$ we construct a new sequence $A_{k+1}$ in the following way. 1. We choose a partition $\{1, \ldots, n\}=I \cup J$, where $I$ and $J$ are two disjoint sets, such that the expression $$\left|\sum_{i \in I} x_{i}-\sum_{j \in J} x_{j}\right|$$ attains the smallest possible value. (We allow the sets $I$ or $J$ to be empty; in this case the corresponding sum is 0 .) If there are several such partitions, one is chosen arbitrarily. 2. We set $A_{k+1}=\left(y_{1}, \ldots, y_{n}\right)$, where $y_{i}=x_{i}+1$ if $i \in I$, and $y_{i}=x_{i}-1$ if $i \in J$. Prove that for some $k$, the sequence $A_{k}$ contains an element $x$ such that $|x| \geq n / 2$. (Iran)

令 $A_{0}=\left(a_{1}, \ldots, a_{n}\right)$ 为有限实数序列。对于每个$k \geq 0$，从序列$A_{k}=\left(x_{1}, \ldots, x_{n}\right)$，我们按以下方式构造一个新序列$A_{k+1}$。 1. 我们选择一个分区 $\{1, \ldots, n\}=I \cup J$，其中 $I$ 和 $J$ 是两个不相交的集合，使得表达式 $$\left|\sum_{i \in I} x_{i}-\sum_{j \in J} x_{j}\right|$$ 获得尽可能小的值。 (我们允许集合 $I$ 或 $J$ 为空；在这种情况下，相应的总和为 0 。)如果有多个这样的分区，则任意选择一个。 2. 我们设置$A_{k+1}=\left(y_{1}, \ldots, y_{n}\right)$，其中如果$i \in I$则$y_{i}=x_{i}+1$，如果$i \in J$则$y_{i}=x_{i}-1$。证明对于某些 $k$，序列 $A_{k}$ 包含元素 $x$，使得 $|x| \geq n / 2$。 (伊朗)