Problem 2560

Lemma. Suppose that all terms of the sequence $(x_{1}, \ldots, x_{n})$ satisfy the inequality $|x_{i}| < a$. Then there exists a partition $\{1,2, \ldots, n\} = I \cup J$ into two disjoint sets such that
$$|\sum_{i \in I} x_{i} - \sum_{j \in J} x_{j}| < a. \tag{1}$$
Proof. Apply an induction on $n$. The base case $n = 1$ is trivial. For the induction step, consider a sequence $(x_{1}, \ldots, x_{n})$ ($n > 1$). By the induction hypothesis there exists a splitting $\{1, \ldots, n-1\} = I' \cup J'$ such that
$$|\sum_{i \in I'} x_{i} - \sum_{j \in J'} x_{j}| < a$$
For convenience, suppose that $\sum_{i \in I'} x_{i} \geq \sum_{j \in J'} x_{j}$. If $x_{n} \geq 0$ then choose $I = I'$, $J = J' \cup \{n\}$; otherwise choose $I = I' \cup \{n\}$, $J = J'$. In both cases, we have $\sum_{i \in I'} x_{i} - \sum_{j \in J'} x_{j} \in [0, a)$ and $|x_{n}| \in [0, a)$; hence
$$\sum_{i \in I} x_{i} - \sum_{j \in J} x_{j} = \sum_{i \in I'} x_{i} - \sum_{j \in J'} x_{j} - |x_{n}| \in (-a, a),$$
as desired.
Let us turn now to the problem. To the contrary, assume that for all $k$, all the numbers in $A_{k}$ lie in interval $(-n / 2, n / 2)$. Consider an arbitrary sequence $A_{k} = (b_{1}, \ldots, b_{n})$. To obtain the term $b_{i}$, we increased and decreased number $a_{i}$ by one several times. Therefore $b_{i} - a_{i}$ is always an integer, and there are not more than $n$ possible values for $b_{i}$. So, there are not more than $n^{n}$ distinct possible sequences $A_{k}$, and hence two of the sequences $A_{1}, A_{2}, \ldots, A_{n^{n} + 1}$ should be identical, say $A_{p} = A_{q}$ for some $p < q$.
For any positive integer $k$, let $S_{k}$ be the sum of squares of elements in $A_{k}$. Consider two consecutive sequences $A_{k} = (x_{1}, \ldots, x_{n})$ and $A_{k+1} = (y_{1}, \ldots, y_{n})$. Let $\{1,2, \ldots, n\} = I \cup J$ be the partition used in this step - that is, $y_{i} = x_{i} + 1$ for all $i \in I$ and $y_{j} = x_{j} - 1$ for all $j \in J$. Since the value of $|\sum_{i \in I} x_{i} - \sum_{j \in J} x_{j}|$ is the smallest possible, the Lemma implies that it is less than $n / 2$. Then we have
$S_{k+1} - S_{k} = \sum_{i \in I} ((x_{i} + 1)^{2} - x_{i}^{2}) + \sum_{j \in J} ((x_{j} - 1)^{2} - x_{j}^{2}) = n + 2(\sum_{i \in I} x_{i} - \sum_{j \in J} x_{j}) > n - 2 \cdot \frac{n}{2} = 0$.
Thus we obtain $S_{q} > S_{q-1} > \cdots > S_{p}$. This is impossible since $A_{p} = A_{q}$ and hence $S_{p} = S_{q}$.