Let A0 = (a1, ..., an) be a finite sequence of real numbers.
For each k >= 0, from the sequence Ak = (x1, ..., xn)
we construct a new sequence A_(k+1) in the following way.
1. We choose a partition {1, ..., n} = I + J,
   where I and J are two disjoint sets, such that
   the expression ∣sum(xi for i in I) − sum(xj for j in J)|
   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)= (y1, ..., yn), where yi = xi + 1 if i in I,
   andy yi = xi − 1 if i in J.

Prove that for some k, the sequence Ak contains an element x such that |x| >= n/2.

=======================================================

So, it should increase the smallest values in large sequences, let's try
a list of length 8 full of ones (8 = 2^3, to make the partitions nice)
and avoid getting the number 4
( 1, 1, 1, 1, 1, 1, 1, 1)
( 0, 0, 0, 0, 2, 2, 2, 2)
( 1, 1, 1, 1, 1, 1, 3, 3)
( 2, 2, 2, 2, 2, 2, 2, 2)
( 1, 1, 1, 1, 3, 3, 3, 3)
( 0, 0, 2, 2, 2, 2, 4, 4)
  -- I already have 4, but can I actually prevent it from growing above all bounds?
(-1,-1, 3, 3, 3, 3, 3, 3)
(-2, 0, 2, 2, 2, 4, 4, 4)
(-3,-1, 1, 3, 3, 3, 3, 5)
... It seems that I am doing something wrong.
I should have kept the sum low, that is certainly possible,
the division can be always made so that the sum does not increase (ideally stays equal)
-- well, there could some issues with keeping absolute value of the sum small
Also, start with zeroes not with ones.

( 0, 0, 0, 0, 0, 0, 0, 0)
(-1,-1,-1,-1, 1, 1, 1, 1)
(-2,-2, 0, 0, 0, 0, 2, 2)
(-3,-1,-1,-1, 1, 1, 1, 3)
(-2,-2,-2,-2, 2, 2, 2, 2)
(-3,-3,-1,-1, 1, 1, 3, 3)
(-4,-2,-2, 0, 0, 2, 2, 4)
  -- I have 4 and -4, but how high will it grow?
(-3,-3,-3,-1, 1, 3, 3, 3)
  -- I am losing sum balance
(-4,-2,-2,-2, 0, 2, 4, 4)

I don't the end of the growth.
Let's try just the sequence of length two.
( 0, 0)
(-1, 1) -- this is the official end
( 0, 2)
( 1, 1)
( 0, 2) -- great, I can cycle

So the idea is that once the numbers are high enough,
it is not possible to find the partition with equal sums of parts,
and that could allow me to "go back".

I guess there is some semi-variant which keeps going one direction while
the partitions are perfectly balanced.
Something like divergence... Sum of squares?
( 0, 0, 0, 0, 0, 0, 0, 0) -- 0
(-1,-1,-1,-1, 1, 1, 1, 1) -- 8
(-2,-2, 0, 0, 0, 0, 2, 2) -- 16
(-3,-1,-1,-1, 1, 1, 1, 3) -- 24
(-2,-2,-2,-2, 2, 2, 2, 2) -- 32
(-3,-3,-1,-1, 1, 1, 3, 3) -- 40
(-4,-2,-2, 0, 0, 2, 2, 4) -- 48
(-3,-3,-3,-1, 1, 3, 3, 3) -- 56
(-4,-2,-2,-2, 0, 2, 4, 4) -- 64
This semivariant fits the experiment.
Could we prove that if the sums are equal, sum of squares increases?
Attempt:
  assume (x1 + ... + xa) = (y1 + ... + yb)
  to prove: (x1+1)^2 + ... + (xa+1)^2 + (y1-1)^2 + ... + (yb-1)^2 > x1^2 + ... xa^2 + y1^2 + ... + yb^2
  (x1+1)^2 + ... + (xa+1)^2 + (y1-1)^2 + ... + (yb-1)^2
  = x1^2 + ... xa^2 + y1^2 + ... + yb^2 + 1*a + 1*b + 2(x1 + ... + xa) - 2(y1 + ... + yb)
  = x1^2 + ... xa^2 + y1^2 + ... + yb^2 + 1*a + 1*b
  QED
So the SoS (sum of squares) increases every step exactly by n (as long as the two partitions are perfectly balanced).
Sanity check: The SoS in the example actually increases by 8 every step.

Now, I would like to generalize it in the case that the partitions are not balanced.
What needs to happen in order no not increase SoS?
  (x1+1)^2 + ... + (xa+1)^2 + (y1-1)^2 + ... + (yb-1)^2 <= x1^2 + ... xa^2 + y1^2 + ... + yb^2
  n + 2(x1 + ... + xa) - 2(y1 + ... + yb) <= 0
  n/2 <= (x1 + ... + xa - y1 - ... - yb)
The imbalance must be at least by n/2.
I hope this is sufficient for one element being at least n/2.
Proof attempt:
* Assume otherwise.
* There is a positive element xi, or a negative element yi (since n/2 <= x1 + ... + xa - y1 - ... - yb)
* Case: there is xi > 0
  * by the assumption, xi < n/2
  * Try putting xi to the other part.
  * then the imbalance is (x1 + ... + xa - y1 - ... - yb - 2*xi) >= n/2 - 2*xi > n/2 - n = -n/2
  * therefore, we decreased the absolute value of the imbalance, which contradicts the assumption
    that the division was optimal.
* Case: there is yi < 0 (should be analogous)
  * by the assumption, yi > -n/2
  * Try putting yi to the other part.
  * then the imbalance is (x1 + ... + xa - y1 - ... - yb + 2*yi) >= n/2 + 2*yi > n/2 - n = -n/2
  * therefore, we decreased the absolute value of the imbalance, which contradicts the assumption
    that the division was optimal.
QED

So we see that until there is an element of abs. value at least n/2, SoS is increasing.
Therefore, there cannot be a cycle in the process. Since every step only increaces / decreases
particular numbers by an integer, there is only finitely many states such that every element
is in absolute value smaller than n/2.
This is contradictory to the idea that the SoS will keep increasing forever while the elements would
stay below n/2.

Problem solved!