Better Know a Theorem: Necklace Splitting

18Oct10

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.

Advertisements


6 Responses to “Better Know a Theorem: Necklace Splitting”

  1. I would also like to add that I heard the problem from Simonyi and Barany who heard this unequal version from Meunier with the upper bound in a slightly stronger version, notably 2PQk/(P+Q), unless I don’t remember it correctly, but at least it matches my construction, nevertheless, I am quite interested in the logarithmic upper bound. (Did I manage to beat the welsh town? Joyce is next!)

    How was Imre’s talk?

  2. I found Imre’s talk was very good, he gave a nice mix of details and intuition. It had the “phase space/test map/target space” approach of equivariant topology, which was a little less mysterious since I’d seen it already in Matoušek’s book. One of his interesting comments was that the topological method is great except when it fails, since it doesn’t tend to give any hint of how to find counterexamples.

    For the upper bound, let g(t) be the number of cuts needed to get ratio t:1-t, and then f(t)=g(t)/k. Observe f(t)=f(1-t); also f(1/n) ≤ 2n/(n+1)<2 for integral n by the construction you mentioned; and f(t*u) <= f(t)+f(u). Now take any rational t=P/R, we'll show f(t) ≤ 3*ceil(log_2(R)). Without loss of generality P/R<1/2. If R is even we reduce the denominator by half, f(t) = f(P/(R/2)*(1/2)) ≤ f(P/(R/2))+1; if R is odd we instead have f(t) = f((1-1/R)*(P/(R-1))) < 2 + f(P/(R-1)) and then we divide the denominator of the latter part by 2.

    Welsh? Joyce? What? James Joyce?

  3. Why is f(t*u) <= f(t)+f(u)? I can only see g(t*u) <= g(t) * g(u).
    I think you also wrote * instead of + later but I can see how the + version would imply the log, just like in the Euclidean algorithm.
    If we denote by F(q) the most number of cuts needed for rationals with denominator q, then I believe the + version for F and I think that is enough using your argument.

    I referred to the long-named town from the earlier post and the long sentence from Ulysses.

  4. You caught typos of +/* – I just fixed them (hopefully). This place is not as fancy as mathoverflow so instead you get 1 Pritchard Point for that! You also get one more for trying to class the blog up with some fine literature.

    To show g(t*u) ≤ g(t) + g(u) or equivalently f(t*u) ≤ f(t) + f(u), cut in ratio t:1-t using at most g(t) cuts, throw away the 1-t part and line up the t part into a new necklace, and cut it in ratio u:1-u, I think one obtains a set of pieces that can be viewed as using at most g(t)+g(u) cuts in the original.


  1. 1 Deconstructing the Pentagon « Dave a.g.p.'s Blog
  2. 2 Deconstructing the Pentagon « Dave a.g.p.'s Blog

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: