Necklace splitting problem
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[1] and Douglas B.
[2] The basic setting involves a necklace with beads of different colors.
The necklace should be divided between several partners (e.g. thieves), 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).
can be proved by the Borsuk-Ulam theorem.
is an odd prime number, the proof involves a generalization of the Borsuk-Ulam theorem.
is a composite number, the proof is as follows (demonstrated for the measure-splitting variant).
measures, each of which values the entire necklace as
In some cases, random necklaces can be split equally using fewer cuts.
Mathematicians Noga Alon, Dor Elboim, Gábor Tardos and János Pach studied the typical number of cuts required to split a random necklace between two thieves.
[4] In the model they considered, a necklace is chosen uniformly at random from the set of necklaces with t colors and m beads of each color.
As m tends to infinity, the probability that the necklace can be split using ⌊(t + 1)/2⌋ cuts or less tends to zero while the probability that it's possible to split with ⌊(t + 1)/2⌋ + 1 cuts is bounded away from zero.
More precisely, letting X = X(t,m) be the minimal number of cuts required to split the necklace.
One can also consider the case in which the number of colors tends to infinity.
When m=1 and the t tends to infinity, the number of cuts required is at most 0.4t and at least 0.22t with high probability.
It is conjectured that there exists some 0.22 < c < 0.4 such that X(t,1)/t converges to c in distribution.
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[5] 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
, a (t − 1)-split exists 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.
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.
-coloring of the real line such that no interval can be fairly split using at most
[6] 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.
[7] An approximation algorithm for splitting a necklace can be derived from an algorithm for consensus halving.
