View source for Necklace splitting problem

[[Image:Collier-de-perles-rouge-vert.svg|thumb|alt=a stylized picture of a necklace, with 8 red and 6 green pearls. The pearls are threaded on to an incomplete elliptical black curve that represents the string. The gap in the curve represents the clasp (open in the diagram) which may be closed when the necklace is placed around the neck. There are two short heavy lines marking breaks in the necklace string. Starting from the left, the necklace is: RRRGRBRRGRRGGBGG, where "R" means "red pearl", "G" means "green pearl", and "B" means "break". The breaks correspond to those in the text|Example of necklace splitting with ''k'' = 2 (i.e. two partners), and ''t'' = 2 (i.e. two types of beads, here 8 red and 6 green).  A 2-split is shown: one partner receives the largest section, and the other receives the remaining two pieces.]]

'''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]]<ref name="Alon 1987">{{cite journal| doi=10.1016/0001-8708(87)90055-7| last=Alon| first=Noga|  title=Splitting Necklaces| journal=[[Advances in Mathematics]]| year=1987| volume=63| issue=3| pages=247&ndash;253| doi-access=free}}</ref> and  [[Douglas B. West]].<ref name="Alon 1986">{{cite journal| last1=Alon| first1=Noga|last2=West | first2=Douglas B.| title=The Borsuk-Ulam theorem and bisection of necklaces| journal=[[Proceedings of the American Mathematical Society]]|date=December 1986| volume=98|issue=4 |pages=623&ndash;628| doi=10.1090/s0002-9939-1986-0861764-9| title-link=Borsuk-Ulam theorem| doi-access=free}}</ref>

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).

== Variants ==
The following variants of the problem have been solved in the original paper:

#'''Discrete splitting''':<ref name="Alon 1987"/>{{rp|Th 1.1}} The necklace has <math>k\cdot n</math> beads. The beads come in <math>t</math> different colors. There are <math>k\cdot a_i</math> beads of each color <math>i</math>, where <math>a_i</math> is a positive integer. Partition the necklace into <math>k</math> parts (not necessarily contiguous), each of which has exactly <math>a_i</math> beads of color ''i''. Use at most <math>(k-1)t</math> cuts. Note that if the beads of each color are contiguous on the necklace, then at least <math>k-1</math> cuts must be done inside each color, so <math>(k-1)t</math> is optimal.
#'''Continuous splitting''':<ref name="Alon 1987"/>{{rp|Th 2.1}}  The necklace is the real interval <math>[0,k\cdot n]</math>. Each point of the interval is colored in one of <math>t</math> different colors. For every color <math>i</math>, the set of points colored by <math>i</math> is [[Lebesgue-measurable]] and has length <math>k\cdot a_i</math>, where <math>a_i</math> is a non-negative real number. Partition the interval to <math>k</math> parts (not necessarily contiguous), such that in each part, the total length of color <math>i</math> is exactly <math>a_i</math>. Use at most <math>(k-1)t</math> cuts.
#'''Measure splitting''':<ref name="Alon 1987"/>{{rp|Th 1.2}}  The necklace is a real interval. There are <math>t</math> different measures on the interval, all absolutely continuous with respect to length. The measure of the entire necklace, according to measure <math>i</math>, is <math>k\cdot a_i</math>. Partition the interval to <math>k</math> parts (not necessarily contiguous), such that the measure of each part, according to measure <math>i</math>, is exactly <math>a_i</math>. Use at most <math>(k-1)t</math> cuts. This is a generalization of the [[Hobby–Rice theorem]], and it is used to get an [[exact division]] of a [[fair cake-cutting|cake]].

Each problem can be solved by the next problem: 
* Discrete splitting can be solved by continuous splitting, since a discrete necklace can be converted to a coloring of the real interval <math>[0,k\cdot n]</math> in which each interval of length 1 is colored by the color of the corresponding bead. In case the continuous splitting tries to cut inside beads, the cuts can be slid gradually such that they are made only between beads.<ref name="Alon 1987"/>{{rp|249}}
* Continuous splitting can be solved by measure splitting, since a coloring of an interval in <math>t</math> colors can be converted to a set <math>t</math> measures, such that measure <math>i</math> measures the total length of color <math>i</math>. The opposite is also true: measure splitting can be solved by continuous splitting, using a more sophisticated reduction.<ref name="Alon 1987"/>{{rp|252–253}}

==Proof==
The case <math>k=2</math> can be proved by the [[Borsuk-Ulam theorem]].<ref name="Alon 1986"/>

When <math>k</math> is an odd [[prime number]], the proof involves a generalization of the Borsuk-Ulam theorem.<ref name="BSS">{{cite journal | title=On a topological generalization of a theorem of Tverberg | author=I.Barany and S.B.Shlosman and A.Szucs | journal=Journal of the London Mathematical Society | year=1981 | volume=2 | issue=23 | pages=158–164 | doi=10.1112/jlms/s2-23.1.158| citeseerx=10.1.1.640.1540 }}</ref>

When <math>k</math> is a [[composite number]], the proof is as follows (demonstrated for the measure-splitting variant). Suppose <math>k=p\cdot q</math>. There are <math>t</math> measures, each of which values the entire necklace as <math>p\cdot q\cdot a_i</math>.    Using <math>(p-1)\cdot t</math> cuts, divide the necklace to <math>p</math> parts such that measure <math>i</math> of each part is exactly <math>q\cdot a_i</math>.   Using <math>(q-1)\cdot t</math> cuts, divide each part to <math>q</math> parts such that measure <math>i</math> of each part is exactly <math>a_i</math>. All in all, there are now <math>p q</math> parts such that measure <math>i</math> of each part is exactly <math>a_i</math>. The total number of cuts is <math>(p-1)\cdot t</math> plus <math>p (q-1)\cdot t</math> which is exactly <math>(pq-1)\cdot t</math>.

==Further results==

===Splitting random necklaces===

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.<ref>{{cite arXiv|title=Random Necklaces require fewer cuts|last1=Alon|first1=Noga|last2=Elboim|first2=Dor|last3=Tardos|first3=Gábor|last4=Pach|first4=János|date=2021|class=math.CO|eprint=2112.14488}}</ref> 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 {{math|⌊(t&nbsp;+&nbsp;1)/2⌋}} cuts or less tends to zero while the probability that it's possible to split with {{math|⌊(t&nbsp;+&nbsp;1)/2⌋&nbsp;+&nbsp;1}} cuts is bounded away from zero. More precisely, letting ''X''&nbsp;=&nbsp;''X''(''t'',''m'') be the minimal number of cuts required to split the necklace. The following holds as m tends to infinity. For any <math>s<(t+1)/2</math>
:<math>\mathbb P(X=s) = \Theta \big( m^{s-(t+1)/2} \big).</math>
For any <math>(t+1)/2<s\leq t</math>
:<math>\mathbb P(X=s) = \Theta ( 1 ).</math>
Finally, when <math>t</math> is odd and <math>s=(t+1)/2</math>
:<math>\mathbb P(X=s) = \Theta \big( (\log m)^{-1} \big).</math>

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.22''t'' with high probability. It is conjectured that there exists some 0.22&nbsp;<&nbsp;''c''&nbsp;<&nbsp;0.4 such that ''X''(''t'',1)/''t''  converges to ''c'' in distribution.

===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''&nbsp;&minus;&nbsp;1 cuts are available, Hungarian mathematician [[Gábor Simonyi]]<ref name="Simonyi 2008">{{cite journal| doi=10.37236/891| last=Simonyi| first=Gábor|title=Necklace bisection with one cut less than needed |journal=Electronic Journal of Combinatorics|volume=15|year=2008|issue=N16| doi-access=free}}</ref> 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''<sub>1</sub> and ''D''<sub>2</sub> of {&nbsp;1,&nbsp;2,&nbsp;..., &nbsp;''t''&nbsp;}, ''not both empty'', such that <math>D_1\cap D_2=\varnothing</math>, a (''t''&nbsp;&minus;&nbsp;1)-split exists such that:

* If colour <math>i\in D_1</math>, then partition 1 has more beads of colour ''i'' than partition 2;
* If colour <math>i\in D_2</math>, 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''.

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

=== Negative result ===
For every <math>k\geq 1</math> there is a measurable <math>(k+3)</math>-coloring of the real line such that no interval can be fairly split using at most <math>k</math> cuts.<ref>{{cite journal|journal=[[Proceedings of the American Mathematical Society]]|title=Splitting necklaces and measurable colorings of the real line|date=November 25, 2008|doi=10.1090/s0002-9939-08-09699-8|doi-access=free|issn=1088-6826|volume=137|issue=5|pages=1593–1599 | last1 = Alon | first1 = Noga|arxiv=1412.7996}}</ref>

===Splitting multidimensional necklaces===

The result can be generalized to ''n'' probability measures defined on a ''d''  dimensional cube with any combination of ''n''(''k''&nbsp;&minus;&nbsp;1) hyperplanes parallel to the sides for ''k'' thieves.<ref>{{Cite journal |
doi=10.1016/j.aim.2008.02.003 | doi-access=free |
last=de Longueville| first=Mark|author2=Rade T. Živaljević|title=Splitting multidimensional necklaces| journal=[[Advances in Mathematics]]| year=2008| volume=218 |
issue=3| pages=926&ndash;939 |arxiv=math/0610800}}</ref>

===Approximation algorithm===
An approximation algorithm for splitting a necklace can be derived from an algorithm for [[Exact division|consensus halving]].<ref>{{Cite journal|last1=Simmons|first1=Forest W.|last2=Su|first2=Francis Edward|date=February 2003|journal=Mathematical Social Sciences|title=Consensus-halving via theorems of Borsuk-Ulam and Tucker|volume=45|issue=1|pages=15–25|doi=10.1016/s0165-4896(02)00087-2|citeseerx=10.1.1.203.1189}}</ref>

== See also ==
* [[Necklace (combinatorics)|Combinatorial necklace]]
* [[Necklace problem]]
* [[Exact division]]

==References==

{{reflist}}

==External links==
* {{youTube|yuVqxCSsE7c|title="Sneaky Topology"|link=no}}, an introductory video presenting the problem with its topological solution.

[[Category:Combinatorics on words]]
[[Category:Discrete geometry]]
[[Category:Fair division]]
[[Category:Mathematical problems]]