Necklace Bisection with One Cut Less than Needed

TL;DR

Simonyi proves a necklace-bisection variant: if a fair split with at most \(k-1\) cuts is impossible, then for any prescribed disjoint color sets \(D_1,D_2\) (not both empty) there is a \(k-1\)-cut bisection giving each thief more of the colors in their assigned set, with the rest divided equally. The proof adapts Alon–West’s Borsuk–Ulam argument using a Tucker–Bacon theorem variant.

Key findings

• Main corollary: Given a necklace with an even number of beads in each of \(k\) colors, if no bisection using at most \(k-1\) cuts gives a fair bipartition, then for any prescribed disjoint subsets \(D_1,D_2\) of the color set, not both empty, there exists a bisection using at most \(k-1\) cuts such that partition class \(j\) gets more beads of color \(i\) iff \(i\in D_j\), while the rest is divided equally.
• Theorem 2: For continuously integrable \(g_1,\dots,g_k:[0,1]\to\mathbb R\), either there exist \(0=z_0\le z_1\le\cdots\le z_{k-1}\le z_k=1\) and \(\delta_1,\dots,\delta_k\in\{+1,-1\}\) with \(\sum_{i=1}^k \delta_i\int_{z_{i-1}}^{z_i} g_j=0\) for all \(1\le j\le k\), or for every \(\beta_1,\dots,\beta_k\in\{+,-,0\}\) not all \(0\), there exist such \(z_i,\delta_i\) with the sign of \(\sum_{i=1}^k \delta_i\int_{z_{i-1}}^{z_i} g_j\) equal to \(\beta_j\) for every \(1\le j\le k\).
• Remark: Corollary 3 generalizes the original necklace bisection theorem. With \(k\) cuts, add a fictitious extra color and choose \(D_1\) to contain only this new color while \(D_2\) is empty; then the existing \(k\) colors can be fairly divided. Similarly, Theorem 2 generalizes the Hobby–Rice theorem.
• The proof combines Alon and West’s simple proof of the original statement with a variant of the Borsuk–Ulam theorem due to Tucker and Bacon.

Methods

• Theoretical combinatorics/topology paper; no empirical data or sample.
• Proves Theorem 2 by encoding \(x=(x_1,\dots,x_k)\in S^{k-1}\) as \(z_i(x)=\sum_{j=1}^i x_j^2\) and \(\delta_i(x)\) having the same sign as \(x_i\), then defining open sets \(A_j\) on \(S^{k-1}\) by \(x\in A_j\) iff \(\sum_{i=1}^k \delta_i(x)\int_{z_{i-1}(x)}^{z_i(x)} g_j>0\).
• If no zero point exists, applies the Tucker–Bacon theorem to \(B:=\{i:\beta_i=+\}\) and \(C:=\{i:\beta_i=-\}\); Corollary 3 follows from Theorem 2 as the original necklace bisection theorem follows from Hobby–Rice, viewing \(g_i\) as mass functions for beads of color \(i\) on the unit interval.

Limitations

• Stated: the paper is concerned only with the case of two thieves; many-thief generalizations are cited but not addressed here.
• Stated: deriving Corollary 3 from Theorem 2 may involve rounding problems, which the paper says are “not very difficult to resolve.”
• Stated/evident: the Tucker–Bacon theorem variant is given only with a “Sketch of proof,” and the paper relies on cited topological and necklace-splitting literature for full details.