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