Splitting necklaces

✍ Scribed by Noga Alon

• Book ID: 102621712
• Publisher: Elsevier Science
• Year: 1987
• Tongue: English
• Weight: 381 KB
• Volume: 63
• Category: Article
• ISSN: 0001-8708
• DOI: 10.1016/0001-8708(87)90055-7

✦ Synopsis

Let N be an opened necklace with ha, beads of color i, 1 < i $ t. We show that it is possible to cut N in (k -1). t places and partition the resulting intervals into k collections, each containing precisely ai beads of color i, 1 6 i < t. This result is best possible and solves a problem of Goldberg and West. Its proof is topological and uses a generalization, due to Barany, Shlosman and Sziics, of the Borsuk-Ulam theorem. By similar methods we obtain a generalization of a theorem of Hobby and Rice on L,-approximation.