Let be a line segment of length broken into pieces of length at most . It’s easy to break into blocks\u00a0(using the preexisting breakpoints) that differ in length by at most (break at the nearest available point to , etc.).<\/p>\n

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. \u00a0Is this achievable in general?<\/p>\n

In today’s combinatorics seminar Imre B\u00e1r\u00e1ny described joint work with\u00a0Victor Grinberg which says that the answer is yes.<\/p>\n

<\/p>\n

The proof is algorithmic. \u00a0Start with any partition of into parts. \u00a0If the difference in length between the smallest and largest parts is at most then we’re done, so assume not. \u00a0Fix a longest block and let be a shortest block. \u00a0Suppose without loss of generality that is to the right of . \u00a0Increase the length of by stealing one piece from the part to the left of . \u00a0Repeat this process until either we find a good partition of , or we steal a piece from . \u00a0On each iteration a piece moves away from , so one of these must occur in finite time.<\/p>\n

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 . \u00a0So when is destroyed there are either fewer blocks of maximal length, or the number of blocks of maximal length has decreased. \u00a0There 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.<\/p>\n","protected":false},"excerpt":{"rendered":"

Let be a line segment of length broken into pieces of length at most . It’s easy to break into blocks\u00a0(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 … <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[4],"tags":[33],"_links":{"self":[{"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/posts\/194"}],"collection":[{"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/comments?post=194"}],"version-history":[{"count":0,"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/posts\/194\/revisions"}],"wp:attachment":[{"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/media?parent=194"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/categories?post=194"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/tags?post=194"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}