Necklace bisection with one cut less than needed
The electronic journal of combinatorics, Tome 15 (2008)
Voir la notice de l'article provenant de la source The Electronic Journal of Combinatorics website
Zbl EuDML
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.
Gábor Simonyi. Necklace bisection with one cut less than needed. The electronic journal of combinatorics, Tome 15 (2008). doi: 10.37236/891
@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/}
}
Cité par Sources :