Necklace splitting theorem

Remarks

For $k = 2$ the result follows from the Borsuk–Ulam theorem. Model the necklace as the interval $[0, 1]$, with each bead a short subinterval. A point $x$ of the sphere $S^t \subset \R^{t+1}$ encodes a cut into $t+1$ consecutive pieces of lengths $x_1^2, \dots, x_{t+1}^2$. The sign of $x_j$ tells which of the two people gets piece $j$. For each colour, take the amount the first person gets minus half the total; this defines an odd map $S^t \to \R^t$. By Borsuk–Ulam it has a zero, which is a fair split with at most $t$ cuts. A final step moves the cuts to bead boundaries. The general case is due to Noga Alon, by induction on the prime factors of $k$ using a generalisation of Borsuk–Ulam.

The bound is sharp: if the beads of each colour lie in one contiguous block, each block needs $k - 1$ cuts.

Going deeper

For a student

This is a standard showcase of topological methods in combinatorics, next to Lovász's proof of the Kneser conjecture. The continuous version, where colours are replaced by measures on an interval, is the form to which Borsuk–Ulam applies directly, much as in the ham sandwich theorem. The bound $(k - 1) t$ cannot be lowered in general, as the example of contiguous colour blocks shows.