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.