\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
%\def\frac#1 #2 {{#1\over #2}}
\def\emph#1{{\it #1}}
\def\em{\it}
\nopagenumbers
\noindent
%
%
{\bf Necklace Bisection with One Cut Less than Needed}
%
%
\medskip
\noindent
%
%
{\bf G\'abor Simonyi}
%
%
\vskip 5mm
\noindent
%
%
%
%
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.



\bye

.