Let be a line segment of length
broken into pieces of length at most
. It’s easy to break
into
blocks (using the preexisting breakpoints) that differ in length by at most
(break at the nearest available point to
,
etc.).
In the case where each piece has length and the number of pieces isn’t divisible by
, we can’t possibly do better than a maximum difference of
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 into
parts. If the difference in length between the smallest and largest parts is at most
then we’re done, so assume not. Fix a longest block
and let
be a shortest block. Suppose without loss of generality that
is to the right of
. Increase the length of
by stealing one piece from the part to the left of
. Repeat this process until either we find a good partition of
, or we steal a piece from
. On each iteration a piece moves away from
, so one of these must occur in finite time.
At each stage we add a piece of length at most to a block of length more than
shorter than
, so we never create new blocks of length at least that of
. So when
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.