Necklace splitting problem

another application in combinatorics

Uses your system voice; voice and rate in settings.

Q6985587Snapshot

≈ 4 min read

Names in other languages

  • FrançaisProblème du partage d'un collier
  • Українськазадача про розрізання намиста
  • РусскийЗадача о разрезании ожерелья
  • EnglishNecklace splitting problem

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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

Proof

The case k=2 can be proved by the Borsuk-Ulam theorem. When k is an odd prime number, the proof involves a generalization of the Borsuk-Ulam theorem. When k is a composite number, the proof is as follows (demonstrated for the measure-splitting variant).

Suppose k=p\cdot q . There are t measures, each of which values the entire necklace as p\cdot q\cdot a_i . Using (p-1)\cdot t cuts, divide the necklace to p parts such that measure i of each part is exactly q\cdot a_i . Using (q-1)\cdot t cuts, divide each part to q parts such that measure i of each part is exactly a_i . All in all, there are now p q parts such that measure i of each part is exactly a_i . The total number of cuts is (p-1)\cdot t plus p (q-1)\cdot t which is exactly (pq-1)\cdot t .

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. 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 cuts or less tends to zero while the probability that it's possible to split with cuts is bounded away from zero. More precisely, letting X = X(t,m) be the minimal number of cuts required to split the necklace. The following holds as m tends to infinity.

For any s \mathbb P(X=s) = \Theta \big( m^{s-(t+1)/2} \big). For any (t+1)/2 \mathbb P(X=s) = \Theta ( 1 ). Finally, when t is odd and s=(t+1)/2 \mathbb P(X=s) = \Theta \big( (\log m)^{-1} \big).

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  1 and D 2 of { 1, 2, ...,  t }, not both empty, such that D_1\cap D_2=\varnothing , a (t − 1)-split exists such that: If colour i\in D_1 , then partition 1 has more beads of colour i than partition 2; If colour i\in D_2 , 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 1 and D 2 , not both empty, there exists a (t − 1)-split so that thief 1 gets more beads of types in his preference set D 1 than thief 2; thief 2 gets more beads of types in her preference set D 2 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 1 consist of the fictitious colour and D 2 empty.

Then Simonyi's result shows that there is a t-split with equal numbers of each real colour.

Approximation algorithm

An approximation algorithm for splitting a necklace can be derived from an algorithm for consensus halving.

, an introductory video presenting the problem with its topological solution.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1372584138 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot necklace-splitting-problem-787374-bb73875f8a4ce003 · hash bb73875f8a4ce003d728baa5304f210dc9bdfa5ce593227f57955ad05fed99e2 · captured 1788249522.0 · version history

Cite this page as: encyclopegia.org, “Necklace splitting problem”, snapshot necklace-splitting-problem-787374-bb73875f8a4ce003. https://encyclopegia.org/a/necklace-splitting-problem

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.