Let $n,k$ be any positive integers. Given real numbers $0\leq a_1,\dots,a_n\leq C$, is it always possible to partition them into $k$ blocks, where each block contains consecutive elements of the sequence, so that the sums of any two blocks differ by at most $C$? If not, what is the best bound?

Remark that this difference may need to be as large as $C$, such as when $a_1=C$ and $a_2=\dots=a_n=0$. An idea is to start with any partition and try to reduce this difference, but since each block needs to contain consecutive elements it is not clear how far the difference can be reduced.

Edit: A difference of $2C$ can be achieved, as shown by Alex Ravsky below. So the bound is between $C$ and $2C$.


If some of the blocks may be empty then we can achieve a partition with the difference at most $2C$ and may be this bound is tight (I’ll think about it). We shall proceed as follows. For the simplicity we assume that all $a_i$’s are positive. Put $a=\frac 1k \sum_{i=1}^n a_i$, $n(0)=0$, $S_0=0$, and for each $1\le j\le k$ let $n(j)$ be the smallest number such that $S_j=\sum_{i=1}^{n(j)} a_i\ge \frac jk a$, and $A_j=\{a_{n(j-1)},\dots, a_{n(j)}\}$ (the set $A_j$ is non-empty provided $a\ge kC$). Then $s_j=\sum_{a_i\in A_j} a_i =S_j-S_{j-1}$ and

$$\frac ak-C=\frac jk a-\left(\frac {j-1}k a+C\right)\le S_j-S_{j-1}\le \left(\frac {j}k a+C\right)- \frac {j-1}k a=\frac ak+C.$$

So $|s_j-s_{j’}|\le 2C$ for any $1\le j, j’\le k$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.