On the placement of a number of strings in a cllection of hats

Abstract

The following problem is considered in this paper: Suppose k strings of unit length are to be distributed amongst x hats. If cuts in the strings are allowed, how should the string (parts) be distributed amongst the hats so that, if the shortest string is removed from each hat, the remaining (combined) string length in the hat with the most string is as small as possible? We solve this problem for a number of special cases (i.e. for certain values of x and k) and provide good bounds on the solution for the remaining cases.

Keywords: String, cutting, partitioning

Quaestiones Mathematicae 31(2008), 359–373