PROBLEM Of splitting a necklace between two thieves:
Two thieves want to share equally the stones of a necklace ( an open circle).
The necklace has $s$ types of stones ( each type of stone appears an even number of time.).
They want to minimize the number of cuts ( the link are costly and they do not want to make a mess of it).
Show that it is always possible to achieve the split using $s$ cuts.
SOLUTIONS:
For $s=2$ a combinatorial solution is not too difficult.
For any $s$, a topological/linear algebra proof exists ( a nice exposition by Jiri Matousek in reference below.)
https://www.amazon.com/Using-Borsuk-Ulam-Theorem-Combinatorics-Universitext/dp/3540003622
Though by now there seem to be a combinatorial proof.
AT:
Pálvölgyi, Dömötör, Combinatorial necklace splitting, Electron. J. Comb. 16, No. 1, Research Paper R79, 8 p. (2009). DOI: 10.37236/168, eudml. ZBL1186.05017, MR2529788.
Yet I believe it might be of interest as a problem that had no combinatorial proof for a while.
