# Low difference between sums of blocks

Let $n,k$ be any positive integers. What is the lowest $r$ (possibly depending on $n,k$) such that given real numbers $0\leq a_1,\dots,a_n\leq 1$, it is 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 $r$?

Taking the example when $a_1=1$ and $a_2=\dots=a_n=0$, we need $r\geq 1$. On the other hand, $r\leq 2$ as we can use an algorithm where we process numbers from left to right and create a new block each time the total sum exceeds $\frac{i}{k}(a_1+\dots+a_n)$ for $1\leq i\leq n-1$.

I suspect this problem must have been studied before. Are there any references?

• It's not clear to me that your algorithm proves r≤2 unless, perhaps, you are more careful in how you describe it. For example, with n= 9 and k=3 it looks like the sequence 1, 1, 1-x, 1, 1, 1, 1-x, 1, 1 will give blocks of weight 4-x, 4-x and 1. Letting x tend to zero gives a difference converging to 3. Nov 3 '16 at 13:40
• @JonNoel For your example, the algorithm I described should give blocks of weight $4-x$, $3-x$ and $2$. (Remember that in the algorithm we look at the total sum, not the sum of each block.)
– pi66
Nov 3 '16 at 15:29
• This resembles a bit bin packing problem. Nov 4 '16 at 16:24

I believe this paper addresses your question, and establishes $r=1$ (in your notation): They say "it is easy to see" that $|b_i-b_j| \le 2$ (your $r \le 2$) by what appears to be the algorithm you sketch. Then they prove their main theorem as in the abstract, and show that it is essentially the best possible result.