Swapping numbers to maintain difference Non-negative real numbers $x_1,\dots,x_n$ are written on the left side of the board, and $y_1,\dots,y_n$ on the right side. Each number is at most $1$. It is known that $|\sum_i x_i - \sum_i y_i| \le 1$. Is it certain that we can swap $n$ pairs of numbers, one after another, so that the difference between the sums of the two sides remains at most $1$ throughout, and at the end all numbers from the left side end up on the right and vice versa?
A possible approach is to use induction, by showing that we can make the first swap and maintaining the difference of $\le 1$. If $\sum_i x_i \ge \sum_i y_i$, there is some pair $(x_j,y_k)$ such that $x_j \ge y_k$, but swapping these two does not guarantee that the difference will remain $\le 1$.
 A: We will show that at each step in the process of swapping the two sets, there is always one possible swap between the elements that have not been swapped yet.
So we are in a situation where we have $k > 0$ numbers still to swap on each side, and the difference $\sum_i x_i-y_i \; = \; s \in [-1, 1]$. We want to show that there is one possible swap after which the difference is $s' \in [-1, 1]$.
For this to be possible, we just need one pair of swappable elements $(x_j, y_k)$ such that $x_j-y_k \in [\frac {s-1} 2, \frac {s+1} 2]$: the new sum will be
$s' \in [s-2\frac {s+1} 2, s-2\frac {s-1} 2]=[-1,1]$.
By contradiction, let's suppose all differences of swappable elements are outside $[\frac {s-1} 2, \frac {s+1} 2]$.
If $k=1$, this is impossible: it would mean the sum after all swaps is outside $[-1,1]$, and this sum is the opposite of the sum before all swaps, which is in $[-1,1]$. So $k\ge2$.
If all differences have the same sign, we have the same problem as for $k=1$: the final sum after all swaps have been made would be outside $[-1,1]$.
So we have at least two differences with opposite signs:
$x_a-y_b < \frac {s-1} 2$, and $x_c-y_d > \frac {s+1} 2$.
Then $y_b > x_a-\frac {s-1} 2 \ge 0-\frac {s-1} 2 = \frac {1-s} 2$.
$x_c-y_b \le 1-y_b < 1-\frac {1-s} 2 = \frac {s+1} 2$.
$x_c > \frac {s+1} 2 + y_d \ge \frac {s+1} 2$.
As $y_b \le 1$, $x_c-y_b > \frac {s+1} 2 - 1 = \frac {s-1} 2$.
So $x_c-y_b \,\in \;]\frac {s-1} 2, \frac {s+1} 2[$.
This is in contradiction with our hypothesis that all differences are outside $[\frac {s-1} 2, \frac {s+1} 2]$.
