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.