John has a string of paper where $n$ real numbers $a_i \in [0, 1]$, for all $i \in \{1, \ldots, n\}$, are written in a row. Show that for any given $k < n$, he can cut the string of paper into non-empty $k$ pieces, between adjacent numbers, in such a way that the sum of the numbers on each piece does not differ from any other sum by more than $1$.
Problem
Source: Baltic Way 2021, Problem 10
Tags: combinatorics, combinatorics proposed
13.01.2022 05:47
We cut the string of paper into $k$ non-empty pieces, regardless if it satisfies the condition or not. Let $P_1,\dots, P_k$ denote the $k$ pieces from left to right, and let $S_i$ be the sum of all numbers on $P_i$ for all $i = 1,\dots,k$. Let the sequence of sums be $S = (S_1, S_2,\dots, S_k)$. Assume that we can move numbers across cuts. We perform the following algorithm: Step $1$: Find $m \le k$ such that $S_m = \text{max}\{S_1,\dots, S_k\}$. Step $2$: If $S_m - \text{min}\{S_1,\dots,S_k\} \le 1$, then we are done. Step $3$: If $S_m - \text{min}\{S_1,\dots,S_k\} > 1$, let $P_a$ be the piece closest to $P_m$ such that $S_a = \text{min}\{S_1,\dots,S_k\}$. If $a < m$, we move the first number of $P_{a+1}$ to $P_a$, and if $a > m$, we move the last number of $P_{a-1}$ to $P_a$. If $|a-m| = 1$, we proceed to Step $1$, otherwise, we proceed to Step $2$. Let the resulting sequence of sums be $S’ = (S_1’, S_2’,\dots, S_k’)$. We see that in step $3$, if $a < m$, $S_{a+1}’ < S_{a+1} \le S_m$, and if $a > m$, $S_{a-1}’ < S_{a-1} \le S_m$. Also, $S_a’ = S_a + a_j \le S_a + 1 < S_m$ for some $j$. Thus, all sums $S_i’$ are at most $S_m$ and no new piece with sum $S_m$ is created. Also, $\text{max}\{S_1,\dots, S_k\}$ does not increase during the algorithm. Also, it is possible that one of the pieces $P_h$ can become empty. Then since $S_h = 0 = \text{min}\{S_1,\dots,S_k\}$, the next time Step $3$ is applied, $a = h$ and $P_h’$ would be non-empty, although it is possible that one of its neighbors would be empty. Thus, at any point in the algorithm, at most one piece can be empty. Claim: After applying Step $3$ for a finite number of times, $S_m$ would decrease. Proof: Let $t_1,\dots, t_k$ be the number of elements in $P_1,\dots, P_k$. Then $\sum_{i=1}^k |i-m|t_i$ increases by $1$ every time Step $3$ is applied when $S_m$ remains the same, and $\sum_{i=1}^k |i-m|t_i \le \sum_{i=1}^k (k-1)n = nk(k-1)$. Thus, $S_m$ eventually has to decrease. When $S_m$ decreases, the algorithm goes back to Step $1$, and either $\text{max}\{S_1,\dots, S_k\}$ decreases, or the number of pieces with a maximal sum decreases. Note that $\text{max}\{S_1,\dots, S_k\}$ can only take finitely many values (at most $2^n$), so the algorithm eventually has to stop at Step $2$, where $\text{max}\{S_1,\dots, S_k\} - \text{min}\{S_1,\dots,S_k\} \le 1$. In the final resulting sequence $S = (S_1, S_2,\dots, S_k)$, if there is still an empty piece $P_h$, i.e. $S_h = 0$, then all sums $S_i$ are in $[0, 1]$. Since there are $k < n$ pieces, there must exists a piece with at least two elements. So we split that piece into two non-empty pieces and discard the empty piece. Since splitting the piece does not increase $\text{max}\{S_1,\dots, S_k\}$, the condition $\text{max}\{S_1,\dots, S_k\} - \text{min}\{S_1,\dots, S_k\} \le 1$ is still satisfied, and we are done.