Considering the convex function $ f$:$ f(x_1,x_2,...,x_n)=\sum_{k=1}^{n}x_k^2$ and assume the opposite assertion.We will get a contradiction quickly

hxy09 wrote: Considering the convex function $ f$:$ f(x_1,x_2,...,x_n) = \sum_{k = 1}^{n}x_k^2$ and assume the opposite assertion.We will get a contradiction quickly Could you elaborate?

Let the funktion $ f(A_k)$ be $ f(A_k)=\sum x_k^2$. f(x) is strict increasing. Assume not so $ f(A_k)\leq(A_k+1)$ we have $ \sum (x_i+1)^2+\sum (x_j-1)^2\leq\sum x_k^2$. Hence $ n \leq2*(\sum x_j-\sum x_i)$ and $ \frac{n}{2} \leq\sum x_j-\sum x_i$, where $ |\sum x_j-\sum x_i|$ is the smallest possible. Now if every $ |x_k|$ is less than $ \frac{n}{2}$, then let $ |z|$ be the greatest number from $ |x_1|,|x_2|...|x_k|$ and we put $ z$ into set $ I$ and every other number one by one if positive into that set of I and J that has the less sum than the other and if negative into the set of I and J that has the greater sum than the other. It's easy to see that $ |\sum x_i-\sum x_j|$ is always less than |z| which is less than $ \frac{n}{2}$, contradiuction to $ \frac{n}{2} \leq\sum x_j-\sum x_i$ is the smallest. Hence f(x) is strict increasing and so it's clear that there is a k so that $ A_k$ satisfield the condiction.

Assume all numbers belong in $(-n/2,n/2)$ always. Given a sequence $A_k=(x_1,...,x_n)$ define $f(A_k)=x_1^2+...+x_k^2$, and notice $f(A_{k+1}) = \sum_{i \in I} (x_i+1)^2 + \sum_{i \in J} (x_i-1)^2 = f(A_k)+n-2(I-J)$, where $I,J$ denote the sums of the sets $I$ and $J$ for convenience. Notice that each individual number has only $n$ "possibilities", since the fractional part is constant. Therefore eventually some configuration will repeat, and therefore $f(A_k)=f(A_{k+m})$ for some $k,m$. This means that $I-J$ has an average value of $n/2$ when it goes from $A_k$ to $A_{k+m}$. Therefore there exists some $I-J \ge n/2$. However, when this happens, if $0 < a \in I$, which must exist, then define $I'=I-a$, $J'=J+a$ and since $a<n/2$, we get $|I'-J'| < |I-J|$, a contradiction. Hence, done.

Let $\{ m\}$ denote the fractional part of a real number $m$. Also, for $A_k=(x_1,..., x_n)$ let $s_k=\sum_{i=1}^n x_i^2$. Consider the values of $\{ \sum_{i\in I} a_i - \sum_{j\in J} a_j\}$ where $I\cup J$ is a partition of the first $n$ integers. If $M$ is the minimal value, then we claim that as long as $A_k$ contains no element $x$ with $|x|\ge n/2$, we have $s_{k+1}\ge s_k + 2M$. Note that the fractional part does not change if the $a_i$ are replaced by $x_i$, as $a_i-x_i$ is an integer for all $i$. Suppose no element of $A_k$ has absolute value at least $n/2$. Then let $A_{k+1}=(y_1,...,y_n)$. We have $$\sum_{i=1}^n y_i^2=\sum_{i\in I} (x_i+1)^2+\sum_{j\in J} (x_j - 1)^2$$$$s_{k+1}=s_k + n + 2\left(\sum_{i\in I} x_i - \sum_{j\in J} x_j\right)$$We claim that $$n + 2\left(\sum_{i\in I} x_i - \sum_{j\in J} x_j\right)>0$$which implies that $$n + 2\left(\sum_{i\in I} x_i - \sum_{j\in J} x_j\right)\ge 2\{ \sum_{i\in I} x_i - \sum_{j\in J} x_j\} = 2\{ \sum_{i\in I} a_i - \sum_{j\in J} a_j\} \ge 2M$$To prove that the sum is always positive, suppose that $I\cup J$ was the optimal partition and $n + 2\left(\sum_{i\in I} x_i - \sum_{j\in J} x_j\right)\le 0$. Then it follows $S=\sum_{i\in I} x_i - \sum_{j\in J} x_j \le -n/2$. But then if we add a positive element to $I$ from $J$ (or remove a negative element from $I$ and add it to $J$), say $x_k$, then the sum increases by $2|x_k|$. But then note $2|x_k| < n$ by definition. If $|S|$ is optimal, then $|S|\le |S+2|x_k||$. Since $S$ is negative, it follows $S+2|x_k| \ge -S$. But then this implies $|x_k|\ge -S \ge n/2$, contradiction! Thus if $I\cup J$ is the optimal partition, then $n + 2\left(\sum_{i\in I} x_i - \sum_{j\in J} x_j\right)>0$. Thus if $A_k$ has no element $x$ with absolute value at least $n/2$, then $s_{k+1}\ge s_k + 2M$. However, this means that eventually $s_k\ge n^3/4$, which solves the problem as $\sum_{i=1}^n x_i^2\ge n^3/4$ implies for some $x_j$ we have $x_j^2\ge n^2/4$, or $|x_j|\ge n/2$. $\square$

Suppose for the sake of contradiction that $|x|\le n/2$ for all $x\in A_k$ for all $k$. The key idea is to consider \[f(A) = \sum_{x\in A}x^2.\]Indeed, note that \[f(A_{k+1})-f(A_k) = n + 2\left(\sum_{i\in I}x_i - \sum_{j\in J}x_j\right)\]where $A_k=(x_1,\ldots,x_n)$. Lemma: We have \[\left|\sum_{i\in I}x_i - \sum_{j\in J}x_j\right|<\frac{n}{2}.\] Proof: Start with $I=\emptyset$, and add on one element from $A_k$ at a time. We see that \[\sum_{i\in I}x_i - \sum_{j\in J}x_j\]changes by $2x_i<n$ at a time, so at some point, it is less than $n/2$ away from $0$. This shows that there is a partition with difference between the split less than $n/2$, and as $I\cup J$ is the optimal partition, the lemma follows. $\blacksquare$ This implies that \[f(A_{k+1})-f(A_k)>0.\qquad\qquad(\star)\]Now, note that \[f(A_{k+1})-f(A_k)\equiv 2\left(\sum_{i\in I}a_i - \sum_{j\in J}a_j\right)\pmod{1},\]and since there are finitely many partitions $I\cup J$, we see that there is some $\delta\in(0,1)$ such that \[\{f(A_{k+1}-A_k)\}\ge \delta,\]or is an integer. In either case, $(\star)$ implies that \[f(A_{k+1})-f(A_k)\ge\delta.\]Therefore, $f(A_k)$ grows arbitrarily large, in contradiction to the fact that the $|x_i|$s are always bounded. This completes the solution.

Let $A_k=(x_{1k},x_{2k},...,x_{nk})$, where $x_{1k}\leq x_{2k}\leq...\leq x_{nk}$. Lemma. If $|a_1|\leq...\leq |a_n|$ and denote $A=\{a_1,...,a_n\}$ then there exists some $I\in A$ such that $$|\sum_{i\in I}a_i-\sum_{i\notin I}a_i|\leq |a_n|\hspace{20pt}(1)$$Proof. We proceed by induction on $n$. If $n=1$ it is trivial, suppose $n=k$ is true, then for $n=k+1$, there exists some $I\in \{a_1,...,a_{n-1}\}$ satisfying $(1)$. Then if $\sum_{i\in I}a_i\leq \sum_{i\notin I}a_i$ we can just put $a_n$ in $I$, which will imply $$|\sum_{i\in I}a_i-\sum_{i\notin I}a_i|=|a_n|-|\sum_{i\in I}a_i-\sum_{i\notin I}a_i-a_n|\geq a_n$$the other case is similar. $\blacksquare$ Let $s_k=\sum_{i=1}^nx_{ik}^2$, we claim that if $|x_{nk}|<\frac{x}{2}$ then $s_k<s_{k+1}$. Indeed, we have(writing $x_{ik}=x_i$) $$s_{k+1}-s_k=\sum_{i\in I}(x_i+1)^2-x_i^2+\sum_{i\in J}(x_i-1)^2-x_i^2=2(\sum_{i\in I}x_i-\sum_{j\in I}x_i+n>2(-\frac{n}{2})+n=0$$as desired. Hence if such $k$ does not exist then $s_k$ is unbounded, contradiction.

Assume the opposite, so that for any $k$ and any $x \in A_k$, we have $|x| < \frac{n}{2}$. Now we claim that for $A_k = \{x_1 , x_2 , \dots , x_n\}$ and $A_{k+1} = \{y_1 , y_2 , \dots , y_n\},$ $\sum_{i=1}^{n} x_i^2 < \sum_{i=1}^{n} y_i^2,$ if we can prove this claim then we will obviously be done. Note that after constructing $A_{k+1},$ $\sum_{i=1}^{n} x_i^2$ changes by $n + 2(\sum_{i\in I}x_i - \sum_{j\in J}x_j)$. Now we greedily construct a partition of $I' \cup J' = \{1,2, \dots , n\}, I' \cap J' = \emptyset,$ so that $|\sum_{i \in I'}x_i - \sum_{j \in J'} x_j| < \frac{n}{2}$. For this, first start with $x_1$ and put it in $I'$. Then for any $t \geq 2$, put $x_t$ in $I'$ or $J'$ such that $|\sum_{i \in I'}x_i - \sum_{j \in J'} x_j|$ is minimal. Since $|x_i| < \frac{n}{2}$ for any $i$, this greedy construction always keeps the inequality $|\sum_{i \in I'}x_i - \sum_{j \in J'} x_j| < \frac{n}{2}$. So, since $I$ and $J$ were optimal sets, we must have $|\sum_{i \in I}x_i - \sum_{j \in J} x_j| < \frac{n}{2}$ as well. So, $\sum_{i=1}^{n} x_i^2$ changes by $n + 2(\sum_{i \in I}x_i - \sum_{j \in J} x_j) > 0$, and we are done. $\square$

Solved with gabrupro. We spent quite some time on this only because of my brilliant assumption that $(-1)^2 = -1$ Suppose not. Let $S$ denote the sum of squares of the terms of $A_k$, we claim this is always increasing, which would be a contradiction. If $S_i$ and $S_j$ are the sums of numbers in $I$ and $J$, then see that $S$ increases by $2(S_i - S_j) + |I| + |J| = n + 2(S_i - S_j)$. So it suffices to show $S_i - S_j < \frac{n}{2}$, but this is easy to see since otherwise, because all elements in the set are $< \frac{n}{2}$, we can move over a term from $I$ to $J$ while decreasing the sum, which was supposedly minimal. Therefore, $S$ is indeed increasing so we are done. $\blacksquare$

Assume the contrary. The key claim is the following: Claim: $\sum_{i=1}^n x_i^2$ always increases after every new sequence constructed. Proof. Note that we have \begin{align*} \sum_{i=1}^n y_i^2 &= \sum_{i\in I} (x_i+1)^2 + \sum_{i\in I} (x_j+1)^2 \\ &= (x_i^2+2x_i+1) + \sum_{i\in I} (x_j^2-2x_j+1) \\ &= n + \sum_{i=1}^n x_i^2 + 2\left(\sum_{i\in I} x_i - \sum_{j \in J} x_j \right).\end{align*}It suffices to prove that $\sum_{i\in I} x_i - \sum_{j \in J} x_j < \frac{n}{2}.$ Suppose that this is not true; then moving any element $i\in \{1, \ldots, n\}$ to $J$ changes $\sum_{i\in I} x_i - \sum_{j \in J} x_j$ by an amount $-2x_i < -2\cdot \frac{n}{2} = -n$. However, this would imply that this new partitioning creates a lower $\left|\sum_{i\in I} x_i - \sum_{j \in J} x_j\right|$, contradiction. $\blacksquare$ Now notice that each individual $x_i$ can be transformed into finitely many numbers, as it is bounded between $-\frac{n}{2}$ and $\frac{n}{2}$ and must be an integer amount away from it's starting value. This implies that there are finitely many values of $\sum_{i=1}^n x_i^2$ attained, which is a contradiction by the claim.

Assume that all $|x| < \frac{n}{2}$, always. Then, note that \[\sum_{i=1}^n x_{i,k+1}^2 = \sum_{i\in I} (x_{i,k}+1)^2 + \sum_{i\in J} (x_{i,k}-1)^2 = \sum_{i=1}^n x_{i,k}^2 + 2\cdot (\sum_{i\in I} x_{i,k} - \sum_{j\in J} x_j) + n \geq \sum_{i=1}^n x_{i,k}^2 - 2\cdot |\sum_{i\in I} x_{i,k} - \sum_{j\in J} x_j| + n\]Note that $|\sum_{i\in I} x_{i,k} - \sum_{j\in J} x_j| \leq \max |x_i|$. This is because one can sort all of the $x_i$ values, and consider beginning with the largest and if the running total is positive, subtract, and if the running total is negative, add. Note that the set of $|\sum_{i\in I} x_{i,k} - \sum_{j\in J} x_j| $ values is finite and they are also all $<\frac{n}{2}$. Thus, under our initial assumption, $- 2\cdot |\sum_{i\in I} x_{i,k} - \sum_{j\in J} x_j| + n> \epsilon$, always, for some constant value of $\epsilon$. Thus, $\sum_{i=1}^n x_{i,k}^2$ increases by a constant amount at each iteration, so eventually it is at least $n\cdot \frac{n}{2}^2$ and the initial assumption is incorrect, so there must eventually be some $|x| \geq \frac{n}{2}$. $\blacksquare$.

My solution seems different Claim: For any set $S$ with maximal and minimal elements each having absolute value almost $M$, ($M > 0$), we may find a partition $S = I \cup J$ such that \[ \left|\sum_{i\in I}x_i - \sum_{j\in J}x_j\right| \leq M \] Proof: We prove this by induction on $|S|$. It is clear for $|S| = 1$. Suppose it is true for $|S| = k$. Then let $S' = S \cup \{a\}$ ($\left|a\right| \leq M$), then for $S$ if we have partitioned into sets $I$ and $J$, then WLOG $\sum_{i\in I}x_i - \sum_{j\in J}x_j$ is positive (it is less than $M$ however, due to the inductive hypothesis). Then, we add $a$ to $J$, if $a$ is positive, to obtain $J'$ ($S' = I \cup J'$). $M > M-a > \sum_{i\in I}x_i - \sum_{j\in J'}x_j \geq -a \geq -M$, and similarly add $a$ to $I$ if $a$ is negative, and in this way we are done. Now, for the main part of the solution, we assume contradiction. The entry in the index $i$ of $A_k$ can only take finitely many values. This is because, if it is $x_i$, then $x_i-a_i$ must be an integer and $-\frac{n}{2} < x_i < \frac{n}{2}$, thus $x_i$ can take almost $n$ values (if it can take $n+1$ or more values where each consecutive pair of values differs by $1$, then two values differ by $n$ and thus one of them must have absolute value at least $\frac{n}{2}$. So, the set $A_i$ in general can only be one of finitely many sequences. Thus one sequence occurs twice, consider the cycle of sequences that leads to this sequence occurring twice. Each entry (from $x_1$ to $x_n$) in each steps takes up a cycle of values (possibly repeated, for example it may be the sequence $(4.5, 5.5, 6.5, 5.5, 6.5, 5.5, 4.5)$). If the length of the cycle is $2k$ (it must be $2k$ for all $n$ entries) then, in the cycle we consider the difference of elements whom we add one to and elements whom we subtract one from. It is not hard to see that this is $-k$ (say by induction on $k$ since we must turn back at one value so we remove this value and the one that follows this and add $-1$ to the sum). Now summing over all the $n$ indices, the difference of elements for which we move forward and for which we move backward must be $-nk$. But, for each time we go from $A_i$ to $A_{i+1}$, the difference of elements we add one to and the difference of elements we subtract one to has absolute value equal to $\left|\sum_{i\in I}x_i - \sum_{j\in J}x_j\right|$, so this absolute value must be minimum over all partitions since we defined the process in such a way. Thus, summing these over all the $2k$ moves, we get one of these must have absolute value at least $\frac{n}{2}$ (since there sum has value $-nk$ and there are a total of $2k$ such values we are considering). This is a contradiction, considering the claim and our assumption that no value has absolute value exceeding $\frac{n}{2}$, and thus we are done.