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.

The proof is algorithmic. Start with any partition of $L$ into $k$ parts. If the difference in length between the smallest and largest parts is at most $1$ then we’re done, so assume not. Fix a longest block $B$ and let $C$ be a shortest block. Suppose without loss of generality that $C$ is to the right of $B$ . Increase the length of $C$ by stealing one piece from the part to the left of $C$ . Repeat this process until either we find a good partition of $L$ , or we steal a piece from $B$ . On each iteration a piece moves away from $B$ , so one of these must occur in finite time.

At each stage we add a piece of length at most $1$ to a block of length more than $1$ shorter than $B$ , so we never create new blocks of length at least that of $B$ . So when $B$ is destroyed there are either fewer blocks of maximal length, or the number of blocks of maximal length has decreased. There are only finitely many possible lengths for blocks, so by repeating with a new block of maximal length we are guaranteed to find a good partition in finite time.

Leave a Reply Cancel reply