Necklace bisection with one cut less than needed (Q1010671)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Necklace bisection with one cut less than needed |
scientific article |
Statements
Necklace bisection with one cut less than needed (English)
0 references
7 April 2009
0 references
Summary: A well-known theorem of \textit{C.H. Goldberg} and \textit{D.B. West} [SIAM J. Algebraic Discrete Methods 6, 93--106 (1985; Zbl 0558.05008)] 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 \textit{N. Alon} and \textit{D.B. West} [Proc. Am. Math. Soc. 98, 623--628 (1986; Zbl 0614.05005)] to the original statement with a variant of the Borsuk-Ulam theorem due to \textit{A.W. Tucker} [Proc. First Canadian Math. Congr., Montreal 1945, Univ. of Toronto Press, 285--309 (1946; Zbl 0061.40305))] and \textit{P.Bacon} [Can. J. Math. 18, 492--502 (1966; Zbl 0142.20804)].
0 references