Question 32
Let $A_{0} = (a_{1}, \ldots, a_{n})$ be a finite sequence of real numbers. For each $k \geq 0$, from the sequence $A_{k} = (x_{1}, \ldots, x_{n})$ 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} = (y_{1}, \ldots, y_{n})$, 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$.
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} = (y_{1}, \ldots, y_{n})$, 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$.