Block partitions of sequences

Let L be a line segment of length l broken into pieces of length at most 1. It’s easy to break L into k blocks (using the preexisting breakpoints) that differ in length by at most 2 (break at the nearest available point to l/k, 2l/k etc.).

In the case where each piece has length 1 and the number of pieces isn’t divisible by k, we can’t possibly do better than a maximum difference of 1 between blocks.  Is this achievable in general?

In today’s combinatorics seminar Imre Bárány described joint work with Victor Grinberg which says that the answer is yes.

Continue reading “Block partitions of sequences”