Necklace splitting problem

In mathematics, and in particular combinatorics, the necklace splitting problem arises in a variety of contexts including exact division; its picturesque name is due to mathematicians Noga Alon ^[1] and Douglas B. West.^[2]

Suppose a necklace, open at the clasp, has k ·n beads. There are k · a_i beads of colour i, where 1 ≤ i ≤ t. Then the necklace splitting problem is to find a partition of the necklace into k parts (not necessarily contiguous), each of which has exactly a_i beads of colour i; such a split is called a k-split. The size of the split is the number of cuts that are needed to separate the parts (the opening at the clasp is not included). Inevitably, one interesting question is to find a split of minimal size.

Example of necklace splitting with k = 2 (i.e. two thieves), and t = 2 (i.e. two types of beads, here 8 red and 6 green). A 2-split is shown.

Alon explains that

the problem of finding k-splittings of small size arises naturally when k mathematically oriented thieves steal a necklace with k · a_i jewels of type i, and wish to divide it fairly between them, wasting as little as possible of the metal in the links between the jewels.

If the beads of each colour are contiguous on the open necklace, then any k splitting must contain at least k − 1 cuts, so the size is at least (k − 1)t. Alon and West^[1] use the Borsuk-Ulam theorem to prove that a k-splitting can always be achieved with this number of cuts. Alon^[2] uses these and related ideas to state and prove a generalization of the Hobby–Rice theorem.

Further results

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^[3] 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 D₁ and D₂ of { 1, 2, ...,  t }, not both empty, such that , a (t − 1)-split exists such that:

• If colour , then partition 1 has more beads of colour i than partition 2;
• If colour , then partition 2 has more beads of colour i than partition 1;
• If colour i is in neither partition, both partitions have equally many beads of colour i.

I.e. if the thieves have preferences in the form of two "preference" sets D₁ and D₂, not both empty, there exists a (t − 1)-split so that thief 1 gets more beads of types in his preference set D₁ than thief 2; thief 2 gets more beads of types in her preference set D₂ 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 D₁ consist of the fictitious colour and D₂ empty. Then Simonyi's result shows that there is a t-split with equal numbers of each real colour.

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.^[4]

See also

• Combinatorial necklaces
• Necklace problem

References