Necklace bisection with one cut less than needed
The electronic journal of combinatorics, Tome 15 (2008)
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\cup D_2\neq\emptyset$, 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.
@article{10_37236_891,
author = {G\'abor Simonyi},
title = {Necklace bisection with one cut less than needed},
journal = {The electronic journal of combinatorics},
year = {2008},
volume = {15},
doi = {10.37236/891},
zbl = {1163.05310},
url = {http://geodesic.mathdoc.fr/articles/10.37236/891/}
}
Gábor Simonyi. Necklace bisection with one cut less than needed. The electronic journal of combinatorics, Tome 15 (2008). doi: 10.37236/891
Cité par Sources :