TOPICS
Search

Necklace Splitting


Necklace splitting is a division problem for a finite sequence of colored beads. Cuts are made between beads, and each resulting contiguous piece is assigned to one of k recipients. A fair split gives every recipient the same number of beads of each color. The bead order is fixed. The rotational equivalence used to define a necklace is not part of this problem (Alon 1987, p. 247; Numberphile 2019).

Suppose there are t colors and ka_i beads of color i, where k, t, and the a_i are positive integers, k>=2, and 1<=i<=t. The necklace-splitting theorem guarantees a fair split using at most t(k-1) cuts (Alon 1987, p. 247). Every recipient receives exactly a_i beads of color i. The pieces assigned to one recipient need not be consecutive.

The bound is sharp. If each color occupies one contiguous block, then giving all k recipients some of that color requires at least k-1 cuts inside its block. The t color blocks therefore require at least t(k-1) cuts in total. The general existence proof uses an extension of the Borsuk-Ulam theorem (Alon 1987, p. 247).


See also

Borsuk-Ulam Theorem, Cake Cutting

Explore with Wolfram|Alpha

References

Alon, N. "Splitting Necklaces." Adv. Math. 63, 247-253, 1987. https://doi.org/10.1016/0001-8708(87)90055-7.Numberphile. "Necklace Splitting (A Lesson for Jewel Thieves)." Jun. 18, 2019. https://www.youtube.com/watch?v=rwiEiGqgetU.

Cite this as:

Weisstein, Eric W. "Necklace Splitting." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/NecklaceSplitting.html

Subject classifications