As many cuts as colours

One line that halves them both ended its tour of the antipodal argument by mentioning, in a sentence, that two thieves dividing a necklace need no more cuts than there are colours of bead. Two opposite points that agree twice proved the theorem behind that sentence on the sphere. This essay cuts the necklace.

The problem is concrete enough to check completely on small necklaces, and it has a feature the halving line did not: a lower bound. Some necklaces genuinely need every cut the theorem allows, so the count of cuts is not merely sufficient but exact. The number of colours is the answer, not an estimate.

A necklace that needs all three cuts #

A necklace is an open string of beads of several colours, with an even number of beads of each colour. Two thieves want to share it so that each gets exactly half of the beads of every colour. They may cut the string between beads into pieces and hand each piece to one of them, and they want to make as few cuts as possible, because a cut damages the necklace.

With one colour the problem is trivial: one cut in the middle gives each thief half, and it is the one-dimensional version of the halving line — slide a cut along the string, and the imbalance between the two sides changes sign, so it passes through zero, as the intermediate value property of the slope of a single point guarantees. With more colours the pieces have to be handed out cleverly, alternating between the thieves, and the question is how many cuts that can take.

The necklace in the figure has 4 orange, 4 blue and 2 green beads. It cannot be shared fairly with one or two cuts, which was established by trying every way of placing one or two cuts and every way of handing out the resulting pieces. Three cuts suffice: the four pieces go to thieves A, B, A and B in turn, and each receives 2 orange, 2 blue and 1 green.

Reading the necklace from left to right shows why the cuts fall where they do. The two green beads sit together at the end, and they must go to different thieves, so one cut has to separate them; that settles the last cut. The first eight beads, four orange and four blue, must then be shared so that the thief who gets the last green bead also gets exactly half of the orange and blue among them, and with the beads in the order they happen to be in, that takes two more cuts rather than one. Nothing about the order looks special, and that is the point: the difficulty is not in any visible pattern but in the arithmetic of which stretches balance, and the exhaustive search is what establishes that two cuts are not enough.

The one-colour case also explains why a cut count grows with the colours at all. Each cut adds one degree of freedom — a position along the string — and each colour adds one condition, that its beads be split evenly. One free position per condition is the same balance of freedom against demand that let a line halve two shapes but not three, and the sphere in the proof below is exactly the space of those free positions.

A point on the sphere becomes a way of cutting #

Goldberg and West proved in 1985 that a necklace with $t$ colours can always be shared fairly between two thieves with at most $t$ cuts, and Alon and West found a short proof through the Borsuk–Ulam theorem shortly afterwards. The proof is worth seeing, because it turns a point on a sphere into a way of cutting a necklace.

Stretch the necklace out as the interval from 0 to 1, with each colour spread along it. Take a point $x = (x_1, \ldots, x_{t+1})$ on the $t$-dimensional sphere, so that $x_1^2 + \cdots + x_{t+1}^2 = 1$. Cut the interval into $t + 1$ consecutive pieces of lengths $x_1^2, \ldots, x_{t+1}^2$, which add up to 1, and give piece $i$ to thief A if $x_i$ is positive and to thief B if it is negative. Now record, for each of the $t$ colours, how much more of it thief A has than thief B. That is a continuous map from the $t$-sphere to $t$-dimensional space.

Replace $x$ by $-x$ and the pieces stay the same, since the lengths are squares, but every owner swaps, so every difference becomes its negative. The map sends opposite points to opposite values. By Borsuk–Ulam some point $x$ has the same value as $-x$, and a value equal to its own negative is zero. At that point every colour is split evenly, using $t + 1$ pieces, which is $t$ cuts. A short further argument moves each cut to a gap between beads without spoiling the balance, which gives the discrete theorem.

From a continuous split to whole beads #

The argument through the sphere produces cuts anywhere along the interval, including in the middle of a bead. Turning that into a split of real beads is a rounding problem, and it needs its own short argument. Treat each bead as a small stretch of the interval carrying one unit of its colour. Suppose a cut falls inside a bead of some colour. Each thief’s share of that colour is a whole number — half of an even count — so the fraction of the bead one thief receives must be made up by another fraction of a bead of the same colour elsewhere, which means a second cut also lies inside a bead of that colour.

Slide the two cuts together, one forwards and one backwards, so that the fraction one thief gains at the first is exactly what they lose at the second. The balance of that colour is unchanged, and the balance of every other colour is unchanged too, because the cuts stay inside beads of the one colour. Keep sliding until one of the two cuts reaches the edge of its bead. Each slide removes one cut from inside a bead without spoiling the split, and repeating it leaves every cut between beads.

Rounding a fractional division to a whole one while keeping every total exact is the same kind of problem the table inside every quota solves for seats and a lottery over whole assignments solves for tasks: a fractional solution is guaranteed by a continuous argument, and a separate combinatorial step moves it to a whole one without losing what made it good.

A necklace that needs every cut #

The theorem says $t$ cuts are enough. The grouped necklace shows they can be necessary. String all the orange beads together, then all the blue, then the green, then the purple. If no cut falls inside the orange block, that whole block lands in one piece and goes to one thief, who then has all the orange beads — unfair. So every block needs a cut strictly inside it, and with four colours that is at least four cuts.

Four are enough: one through the middle of each block, with the five pieces handed out alternately. The first thief gets one orange, then one blue and one green from the middle pieces, and one purple at the end, in exactly the pattern the figure shows. The upper bound and the lower bound meet, and the grouped necklace is the witness that the theorem’s count is the best possible.

Every necklace, checked #

The theorem can be checked outright on small necklaces, because they can all be listed. With 4 orange and 4 blue beads there are 70 arrangements: 36 can be shared with a single cut and the other 34 need two, and none needs three. With 6 of each there are 924: 400 need one cut and 524 need two. With three colours of 2 beads each there are 90 arrangements, of which 12 need all three cuts.

The largest cases take longer to settle. The 3,150 arrangements of 4 orange, 4 blue and 2 green beads split into 900 needing one cut, 1,690 needing two and 560 needing three; the 2,520 arrangements of four colours with 2 beads each split into 576, 1,128, 744 and 72. In every composition, no necklace needs more cuts than colours, and some necklace needs exactly that many. The count of necklaces needing the maximum is a large share when the colours are few and a small one when they are many — 34 of 70 against 72 of 2,520 — because a random arrangement of many colours usually mixes them enough to share with fewer cuts.

The shares needing the maximum move in an informative way. With two colours, 34 of the 70 necklaces of four beads each need both cuts, about 49 per cent, and 524 of the 924 with six beads each, about 57 per cent: more beads of each colour make it more likely that the colours are interleaved in a pattern one cut cannot balance. With more colours the share drops sharply — 12 of 90, or 13 per cent, for three colours of two beads, and 72 of 2,520, under 3 per cent, for four — because with many colours it becomes likely that some single cut already balances several of them at once. The worst case is guaranteed to occur and is rarely what a random necklace looks like.

Checking every arrangement is not a proof of the theorem, which is about necklaces of every size. It is evidence of the kind a proof by continuity cannot give: the discrete theorem, cut positions restricted to gaps between beads, is exactly what these tables test, and the step from the continuous version to it is the part of the argument most easily got wrong.

A continuous necklace #

The continuous version is the theorem the proof actually establishes. Here two colours are spread along the necklace with densities that rise and fall — one slowly, one three times as fast — and the thieves want half of each. The theorem promises two cuts, and the figure finds them at 0.2444 and 0.6720 of the way along by Newton’s method on the exact amounts of each colour: thief A takes the two outer pieces and thief B the middle one, and each gets half of both colours to twelve decimal places.

This form was proved independently of necklaces by Hobby and Rice in 1965, for a reason that has nothing to do with theft: in approximation theory, a function can be matched in average by one that switches between two values at no more than $t$ points, and the switching points are the cuts. The same theorem appears as a fact about approximating functions and as a fact about sharing loot, which is the characteristic reach of results that come from the Borsuk–Ulam theorem.

More thieves #

With $k$ thieves each wanting an equal share of every colour, Noga Alon proved in 1987 that $(k - 1) \times t$ cuts always suffice. The grouped necklace shows it is best possible for the same reason as before: every block of a colour must now be cut into at least $k$ parts, which takes $k - 1$ cuts inside each of the $t$ blocks.

Three thieves sharing 3 orange and 3 blue beads have 20 possible necklaces; the most any needs is 4 cuts, which is $(3 - 1) \times 2$, and 2 of the 20 need all four. With three colours of 3 beads each there are 1,680 necklaces, needing between 2 and 6 cuts, and 6 of them need the full $(3 - 1) \times 3 = 6$. Alon’s proof needed a stronger version of Borsuk–Ulam, one that uses a symmetry of order $k$ in place of the swap of opposite points, first for $k$ prime and then by combining primes.

Guaranteed, and hard to find #

The smallest necklace of three colours that needs all three cuts has just six beads, and this one is not simply grouped by colour: the beads are mixed, and still no two cuts suffice. Small as it is, finding its split still meant trying the possibilities. That is not laziness in the figure; it reflects a real difficulty.

The Borsuk–Ulam proof guarantees a fair split but gives no efficient way to find one, and there is strong evidence that none exists. Filos-Ratsikas and Goldberg proved in 2018 and 2019 that finding such a split for two thieves, when the number of colours is part of the problem, is complete for a class of search problems called PPA. Those are the problems whose solutions are guaranteed by a parity argument — the principle, familiar from the seven bridges, that a network has an even number of places where an odd number of roads meet. A solution always exists, and finding it is believed to be as hard as any problem of that kind.

That separates necklace splitting from other guaranteed fair divisions. Nobody has a reason to run away proves that a stable matching always exists, and its proof is a fast procedure that finds one. The necklace theorem’s proof is an argument about spheres, and no procedure faster than searching is known.

Fair division, more generally #

The necklace is one case of a broad question: how to divide something among people who value its parts differently. One cuts and the other chooses divides a cake fairly between two people with one cut, and three people and a trimmed piece extends the idea to three with moving knives. In those problems each person has their own valuation, and fairness means nobody prefers another’s share.

The necklace asks for something stronger and more objective — an exactly equal share of every colour — and pays for it in cuts. Consensus halving, the general form, asks to divide a cake into two portions that every one of $t$ people considers exactly half, and the answer is again $t$ cuts, by the same Borsuk–Ulam argument with each person’s valuation playing the role of a colour.

Small necklaces, one way of cutting, one pair of densities #

The exhaustive tables stop at a few thousand necklaces. Every arrangement of each composition drawn was checked, but compositions with more beads or more colours grow too fast to list, and the theorem for them rests on the proof alone.

The cut positions are not unique. A necklace that can be shared with three cuts usually has several ways to do it, and the figures show the first found; the theorem says nothing about which, and a thief with a preference among the ways would need a different argument.

And the continuous figure shows one pair of densities. The Newton solution is exact for those two curves; the theorem is for any densities at all, including ones concentrated at single points, where the discrete and continuous versions meet.

Still open: how many cuts a fair cake needs #

The necklace needs a number of cuts fixed by the number of colours. Envy-free cake cutting — dividing a cake among $n$ people so that nobody prefers anyone else’s piece, each judging by their own valuation — also always has a solution, but the number of steps a procedure needs to find one is wildly uncertain. Aziz and Mackenzie gave the first procedure with a bounded number of steps in 2016, and their bound is a tower of six exponentials in $n$. The best lower bound known is proportional to $n^2$, and nobody knows whether envy-free division really needs anything like the tower or can be done in a number of steps polynomial in $n$.

A count that is exact #

The antipodal theorem usually proves that something exists. Applied to necklaces it proves a count: two thieves never need more cuts than colours, and the necklace grouped by colour needs every one of them, so the count is exactly right. Every necklace of five small compositions obeys it, three thieves obey the version with $(k-1) \times t$ cuts, and the continuous version, found by the same argument, splits two smoothly varying colours with two cuts.

When a guarantee has a matching example, the guarantee is the answer. Borsuk–Ulam supplies the guarantee, the grouped necklace supplies the example, and between them the question of how many cuts is closed — even though the question of where to cut remains hard.