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.)

http://www.amazon.com/Using-Borsuk-Ulam-Theorem-Combinatorics-Universitext/dp/3540003622

Though by now there seem to be a combinatorial proof.
AT : http://www.combinatorics.org/Volume_16/PDF/v16i1r79.pdf

Yet I believe it might be of interest as a problem that had no combinatorial proof for a while.

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.