![]() | ||
Necklace splitting is a picturesque name given to several related problems in combinatorics and measure theory. Its name and solutions are due to mathematicians Noga Alon and Douglas B. West.
Contents
- Variants
- Proof
- One cut fewer than needed
- Negative result
- Splitting multidimensional necklaces
- Approximation algorithm
- References
The basic setting involves a necklace with beads of different colors. The necklace should be divided between several partners, such that each partner receives the same amount of every color. Moreover, the number of cuts should be as small as possible (in order to waste as little as possible of the metal in the links between the beads).
Variants
The following variants of the problem have been solved in the original paper:
- Discrete splitting: The necklace has
k ⋅ n beads. The beads come int different colors. There arek ⋅ a i i , wherea i k parts (not necessarily contiguous), each of which has exactlya i ( k − 1 ) t cuts. Note that if the beads of each color are contiguous on the necklace, then at leastk − 1 cuts must be done inside each color, so( k − 1 ) t is optimal. - Continuous splitting: The necklace is the real interval
[ 0 , k ⋅ n ] . Each point of the interval is colored in one oft different colors. For every colori , the set of points colored byi is Lebesgue-measurable and has lengthk ⋅ a i a i k parts (not necessarily contiguous), such that in each part, the total length of colori is exactlya i ( k − 1 ) t cuts. - Measure splitting: The necklace is a real interval. There are
t different measures on the interval, all absolutely continuous with respect to length. The measure of the entire necklace, according to measurei , isk ⋅ a i k parts (not necessarily contiguous), such that the measure of each part, according to measurei , is exactlya i ( k − 1 ) t cuts. This is a generalization of the Hobby–Rice theorem, and it is used to get an exact division of a cake.
Each problem can be solved by the next problem:
Proof
The case
When
When
One cut fewer than needed
In the case of two thieves [i.e. k = 2] and t colours, a fair split would require at most t cuts. If, however, only t − 1 cuts are available, Hungarian mathematician Gábor Simonyi shows that the two thieves can achieve an almost fair division in the following sense.
If the necklace is arranged so that no t-split is possible, then for any two subsets D1 and D2 of { 1, 2, ..., t }, not both empty, such that
This means that if the thieves have preferences in the form of two "preference" sets D1 and D2, not both empty, there exists a (t − 1)-split so that thief 1 gets more beads of types in his preference set D1 than thief 2; thief 2 gets more beads of types in her preference set D2 than thief 1; and the rest are equal.
Simonyi credits Gábor Tardos with noticing that the result above is a direct generalization of Alon's original necklace theorem in the case k = 2. Either the necklace has a (t − 1)-split, or it does not. If it does, there is nothing to prove. If it does not, we may add beads of a fictitious colour to the necklace, and make D1 consist of the fictitious colour and D2 empty. Then Simonyi's result shows that there is a t-split with equal numbers of each real colour.
Negative result
For every
Splitting multidimensional necklaces
The result can be generalized to n probability measures defined on a d dimensional cube with any combination of n(k − 1) hyperplanes parallel to the sides for k thieves.
Approximation algorithm
An approximation algorithm for splitting a necklace can be derived from an algorithm for consensus halving.