Paper Info
Title
Necklace Bisection with One Cut Less than Needed.
Abstract
A well-known theorem of Goldberg and West states that two thieves can always split a necklace containing an even number of beads from each of k types fairly by at most k cuts. We prove that if we can use at most k-1 cuts and fair splitting is not possible then the thieves still have the following option. Whatever way they specify two disjoint sets D-1, D-2 of the types of beads with D-1 boolean OR D-2 not equal phi it will always be possible to cut the necklace (with k-1 cuts) so that the first thief gets more of those types of beads that are in D-1 and the second gets more of those in D-2, while the rest is divided equally. The proof combines the simple proof given by Alon and West to the original statement with a variant of the Borsuk-Ulam theorem due to Tucker and Bacon.
Year
DOI
Venue
2008
10.37236/891
ELECTRONIC JOURNAL OF COMBINATORICS
DocType
Volume
Issue
Journal
15.0
1.0
ISSN
Citations 
PageRank 
1077-8926
0
0.34
References 
Authors
3
1
Name
Order
Citations
PageRank
Gábor Simonyi124929.78