Better Know a Theorem: Necklace Splitting
Pursuant to my previous post on alternative career paths for math students, I should mention that there is a vibrant range of careers on stealing and splitting necklaces, and proving related theorems. For example, a pair of drunken post-docs break in to the Swatch store and steal a necklace with k different types of gems on it.
Although drunk, the two sticky-fingered postdocs are fair and wish to split the necklace evenly; since they don’t remember the monetary values of all the different kinds of gems, their goal is that for each of the k types of gems, half (rounding up or down) should go to each robber.
In order to split the gems, the necklace must be cut in several places; each robber takes some of the pieces home. How many cuts are needed? It depends on how the gems are arranged, but the following theorem shows what is the worst case.
Theorem (Goldberg & West 1985). At most k cuts are needed.
(Above and later, we model the necklace as having a single clasp that opens and does not need to be cut, so it is like a line rather than a closed circle.) Moreover, if there is a larger group of post-docs,
Theorem (Alon 1987). To split the necklace evenly amongst n thieves, at most (n-1)k cuts are needed.
I became interested in this problem as it turns out to be very similar to a problem that Rico Zenklusen mentioned in a talk about an unrelated algorithmic problem; here is the interesting open problem that showed up.
An Open Question about Asymmetric Robbers. Suppose that we again have two robbers, one of whom did more work than the other, and so the robbers desire to split the gems in some ratio P:Q other than 1:1. How many cuts are needed?
(In this setting, let us assume gems are infinitely divisible, so for example you can cut a diamond into two halves or ratio 30%-70%. Then we seek all gem types divided exactly in ratio P:Q, without any rounding necessary. This makes stating the facts below more natural.)
- The case k=2 is solved: only 2 cuts are needed, the same as the 1:1 case. The paper of Grandoni & Zenklusen linked above gives one proof, and Alon-West 1986 gives another proof.
- For larger k, if P and Q are integral, then by Alon’s theorem we can use (P+Q-1)k cuts into P+Q equal-valued sets, and then afterwards give P to robber 1 and Q to robber 2.
- A somewhat fancier use of Alon’s theorem shows that something like 8 * ln(P+Q)k cuts is sufficient when P and Q are integral.
- An example of Dömötör Pálvölgyi shows that for ratio 2:1, the optimal number of cuts is approximately 4k/3.
There is a lot of space between the known upper and lower bounds: it might be true that 2k cuts is enough for any ratio, or it might be that O(ln(P+Q))k is optimal and irrational ratios are impossible for all k>2.
The methods used to prove the theorems of Goldberg-West and Alon are fascinating; I needed to read a lot of topology to understand the ideas. A nice book of Jiří Matoušek has been a great digestive aid for me. In essence, one reformulates the necklace problems as being about a symmetry-preserving map from one symmetric space to another symmetric space.
In trying to apply these techniques to arbitrary P:Q, a major problem is a lack of symmetry: dividing equally amongst n robbers means that the set of possible “splitting configurations” automatically inherits an n-fold symmetry, but for a ratio like π:1, this is not true. Later this week Imre Bárány will give a talk here at EPFL about some related problems.
Filed under: b.k.a.t., math | 6 Comments