ISL 2007 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)