Necklace splitting problem

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 · ai 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 ai 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.

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 thieves), and t = 2 (i.e. two types of beads, here 8 red and 6 green). A 2-split is shown.

Alon explains that

\ldots the problem of finding k-splittings of small size arises naturally when k mathematically oriented thieves steal a necklace with k · ai 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.

Contents

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 D1 and D2 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.

I.e. 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. 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 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.

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

References

  1. ^ a b Alon, Noga (1987). "Splitting Necklaces". Advances in Mathematics 63 (3): 247–253. doi:10.1016/0001-8708(87)90055-7. 
  2. ^ a b Alon, Noga; West, D. B. (December 1986). "The Borsuk-Ulam theorem and bisection of necklaces". Proceedings of the American Mathematical Society 98 (4): 623–628. 
  3. ^ Simonyi, Gábor (2008). "Necklace bisection with one less cut than needed". Electronic journal of combinatorics 15 (N16). 
  4. ^ de Longueville, Mark; Rade T. Živaljević (2008). "Splitting multidimensional necklaces". Advances in Mathematics 218 (3): 926–939. doi:10.1016/j.aim.2008.02.003. 

Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Necklace problem — The necklace problem is a problem in recreational mathematics, solved in the early 21st century. Contents 1 Formulation 2 Solution 3 References 4 See also …   Wikipedia

  • Necklace (combinatorics) — In combinatorics, a k ary necklace of length n is an equivalence class of n character strings over an alphabet of size k, taking all rotations as equivalent. It represents a structure with n circularly connected beads of up to k different colors …   Wikipedia

  • Necklace — For other uses, see Necklace (disambiguation). A bead crochet necklace made from crochet lace, sterling silver, and freshwater pearls. A necklace is an article of jewellery which is worn around the neck. Necklaces are frequently formed from a… …   Wikipedia

  • Necklace (disambiguation) — A necklace is an article of jewelry worn around the neck. Necklace may also refer to: Necklace (combinatorics) or fixed necklace, a concept in combinatorial mathematics The Necklace , a short story by Guy de Maupassant The Necklace , an episode… …   Wikipedia

  • Théorème de Borsuk-Ulam — En mathématiques, le théorème de Borsuk Ulam est un résultat de topologie algébrique. Il indique que pour toute fonction f continue d une sphère de dimension n, c est à dire la frontière de la boule euclidienne de Rn+1, dans un espace euclidien… …   Wikipédia en Français

  • Noga Alon — 2008 Noga Alon (hebräisch ‏נוגה אלון‎; Pseudonym Alon Nilli; * 1956) ist ein israelischer Mathematiker (Kombinatorik) und Informatiker. Alon promovierte 1983 an der Hebräischen Universität Jerusalem bei Micha Perle …   Deutsch Wikipedia

  • Noga Alon — Born 1956 Israel …   Wikipedia

  • Hobby-Rice theorem — In mathematics, and in particular the study of necklace splitting problems, the Hobby Rice theorem is a result that is useful in establishing the existence of certain solutions. The theoremIf g 1,ldots,g k: [0,1] longrightarrowBbb{R} are given… …   Wikipedia

  • Lake Merritt — Infobox lake lake name = Lake Merritt image lake = Lakemerrit02192006.jpg type = recreation, lagoon, wildlife refuge caption lake =A view looking west toward the Lakeside Apartments District, the Tribune Tower and Downtown Oakland location = East …   Wikipedia

  • Into the West (TV miniseries) — Infobox Television Film bgcolour = name = Into the West image sized = image size = caption = The DVD packaging for Into the West format = Western runtime = 552 minutes creator = director = Robert Dornhelm Simon Wincer Sergio Mimica Gezzan Michael …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”