用户:TNTErick/项链分割

k = 2（即分为两集合）和 t = 2（即八红六绿两种珠子）项链分割的释例。在图例中，其中一个集合不是相连续的，它被拆为左上和右上部分。

项链分割问题（Necklace Splitting Problem）是一类组合学及测度学问题。这个名字取自于它的一个较生动的类比。在复杂度上，一个将t色项链项链分成k分的分割属于NP完全问题。该问题及其主要的解法、证明，皆由以色列数学家诺嘉亚隆及道格拉斯威斯特提出。

一般的项链分割问题将 t 种珠子分成若干段，而将这些段重组成 k 个部分，其中每一段中任一种珠子的颗数须相同，因此又称为k块 t相项链分割(英语：k-wise t-way necklace splitting)。再者，分出的段数愈小，即在项链上动的刀数愈少愈好，如此一来可以“浪费最少的金属炼”。

定义

在原论文中叙述及了以下几种项链分割问题：

1. 离散分割：项链中有 $t$ 种颜色的珠子共 $k\cdot n$ 颗。而颜色 $i\in {1,2,\ldots s}$ 具有 $k\cdot a_{i}$ 颗，其中 $a_{i},n,k$ 为正整数。在 $(k-1)t$ 刀以内，将其分为 $k$ 个不一定连续的部分，使得每一个部分皆具有 $a_{i}$ 颗第 $i$ 色的珠子。考虑最差的状况：所有颜色皆连续，则每一个颜色都须要切 $k-1$ 刀，因此该解已为最优解。
2. 连续分割:这条项链对应到实数区间 $[0,k\cdot n]$。区间上的每一个点都有$t$色中的一种颜色。对每一个颜色 $i\in [t]$，上了色的集合都要是勒贝格可测集而且该集合长度$k\cdot a_{i}$($a_{i}$是非负实数)。Partition the interval to $k$ parts (not necessarily contiguous), such that in each part, the total length of color $i$ is exactly $a_{i}$. Use at most $(k-1)t$ cuts.
3. Measure splitting: The necklace is a real interval. There are $t$ different measures on the interval, all absolutely continuous with respect to length. The measure of the entire necklace, according to measure $i$, is $k\cdot a_{i}$. Partition the interval to $k$ parts (not necessarily contiguous), such that the measure of each part, according to measure $i$, is exactly $a_{i}$. Use at most $(k-1)t$ cuts. This is a generalization of the Hobby–Rice theorem, and it is used to get an exact division of a cake.

前两个情况都分别是下一个情况的特例，因此也可以以下一个问题来解决。如下：

• Discrete splitting can be solved by continuous splitting, since a discrete necklace can be converted to a coloring of the real interval $[0,k\cdot n]$ in which each interval of length 1 is colored by the color of the corresponding bead. In case the continuous splitting tries to cut inside beads, the cuts can be slid gradually such that they are made only between beads.
• Continuous splitting can be solved by measure splitting, since a coloring of an interval in $t$ colors can be converted to a set $t$ measures, such that measure $i$ measures the total length of color $i$. The opposite is also true: measure splitting can be solved by continuous splitting, using a more sophisticated reduction.

Proof

$k=2$时的情况可以用博苏克乌兰定理证明。当$k$是其他质数，也可以用推广了的该定理证明。

而$k$是合成数时， the proof is as follows (demonstrated for the measure-splitting variant). Suppose $k=p\cdot q$. There are $t$ measures, each of which values the entire necklace as $p\cdot q\cdot a_{i}$. Using $(p-1)\cdot t$ cuts, divide the necklace to $p$ parts such that measure $i$ of each part is exactly $q\cdot a_{i}$. Using $(q-1)\cdot t$ cuts, divide each part to $q$ parts such that measure $i$ of each part is exactly $a_{i}$. All in all, there are now $pq$ parts such that measure $i$ of each part is exactly $a_{i}$. The total number of cuts is $(p-1)\cdot t$ plus $p(q-1)\cdot t$ which is exactly $(pq-1)\cdot t$.

Further results

One cut fewer than needed

In the case of two thieves [i.e. k = 2] and t colours, a fair split would require at most t cuts. If, however, only t − 1 cuts are available, Hungarian mathematician Gábor Simonyi shows that the two thieves can achieve an almost fair division in the following sense.

If the necklace is arranged so that no t-split is possible, then for any two subsets D₁ and D₂ of { 1, 2, ...,  t }, not both empty, such that $D_{1}\cap D_{2}=\varnothing$, a (t − 1)-split exists such that:

• If colour $i\in D_{1}$, then partition 1 has more beads of colour i than partition 2;
• If colour $i\in D_{2}$, then partition 2 has more beads of colour i than partition 1;
• If colour i is in neither partition, both partitions have equally many beads of colour i.

This means that if the thieves have preferences in the form of two "preference" sets D₁ and D₂, not both empty, there exists a (t − 1)-split so that thief 1 gets more beads of types in his preference set D₁ than thief 2; thief 2 gets more beads of types in her preference set D₂ than thief 1; and the rest are equal.

Simonyi credits Gábor Tardos with noticing that the result above is a direct generalization of Alon's original necklace theorem in the case k = 2. Either the necklace has a (t − 1)-split, or it does not. If it does, there is nothing to prove. If it does not, we may add beads of a fictitious colour to the necklace, and make D₁ consist of the fictitious colour and D₂ empty. Then Simonyi's result shows that there is a t-split with equal numbers of each real colour.

Negative result

For every $k\geq 1$ there is a measurable $(k+3)$-coloring of the real line such that no interval can be fairly split using at most $k$ cuts.

Splitting multidimensional necklaces

The result can be generalized to n probability measures defined on a d dimensional cube with any combination of n(k − 1) hyperplanes parallel to the sides for k thieves.

Approximation algorithm

An approximation algorithm for splitting a necklace can be derived from an algorithm for consensus halving.

参见

• 集合划分
• Combinatorial necklaces
• Necklace problem

外部链接

• YouTube上的"Sneaky Topology", an introductory video presenting the problem with its topological solution.