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?

  • $\begingroup$ 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. $\endgroup$
    – Jon Noel
    Nov 3 '16 at 13:40
  • 1
    $\begingroup$ @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.) $\endgroup$
    – pi66
    Nov 3 '16 at 15:29
  • 2
    $\begingroup$ This resembles a bit bin packing problem. $\endgroup$
    – Michael
    Nov 4 '16 at 16:24

I believe this paper addresses your question, and establishes $r=1$ (in your notation):

Bárány, Imre, and Victor S. Grinberg. "Block partitions of sequences." Israel Journal of Mathematics, 206.1 (2015): 155-164. (PDF download.)

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.


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.