User:TNTErick/項鍊分割
此用戶頁目前正依照其他维基百科上的内容进行翻译。 (2020年11月5日) |
![a stylized picture of a necklace, with 8 red and 6 green pearls. The pearls are threaded on to an incomplete elliptical black curve that represents the string. The gap in the curve represents the clasp (open in the diagram) which may be closed when the necklace is placed around the neck. There are two short heavy lines marking breaks in the necklace string. Starting from the left, the necklace is: RRRGRBRRGRRGGBGG, where "R" means "red pearl", "G" means "green pearl", and "B" means "break". The breaks correspond to those in the text](http://upload.wikimedia.org/wikipedia/commons/thumb/4/47/Collier-de-perles-rouge-vert.svg/220px-Collier-de-perles-rouge-vert.svg.png)
項鍊分割問題(Necklace Splitting Problem)是一類組合學及測度學問題。這個名字取自於它的一個較生動的類比。在複雜度上,一個將t色項鍊項鍊分成k分的分割屬於NP完全問題。該問題及其主要的解法、證明,皆由以色列數學家諾嘉亞隆[1]及道格拉斯威斯特提出[2]。
一般的項鍊分割問題將 t 種珠子分成若干段,而將這些段重組成 k 個部分,其中每一段中任一種珠子的顆數須相同,因此又稱為k塊 t相項鍊分割(英語:k-wise t-way necklace splitting)。再者,分出的段數愈小,即在項鍊上動的刀數愈少愈好,如此一來可以「浪費最少的金屬鍊」。
定義
[编辑]在原論文中敘述及了以下幾種項鍊分割問題:
- 離散分割:[1]:定理1.1項鍊中有 種顏色的珠子共 顆。而顏色 具有 顆,其中 為正整數。在 刀以內,將其分為 個不一定連續的部分,使得每一個部分皆具有 顆第 色的珠子。考慮最差的狀況:所有顏色皆連續,則每一個顏色都須要切 刀,因此該解已為最優解。
- 連續分割:[1]:Th 2.1這條項鍊對應到實數區間 。區間上的每一個點都有色中的一種顏色。對每一個顏色 ,上了色的集合都要是勒貝格可測集而且該集合長度(是非負實數)。Partition the interval to parts (not necessarily contiguous), such that in each part, the total length of color is exactly . Use at most cuts.
- Measure splitting:[1]:Th 1.2 The necklace is a real interval. There are different measures on the interval, all absolutely continuous with respect to length. The measure of the entire necklace, according to measure , is . Partition the interval to parts (not necessarily contiguous), such that the measure of each part, according to measure , is exactly . Use at most 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 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.[1]:249
- Continuous splitting can be solved by measure splitting, since a coloring of an interval in colors can be converted to a set measures, such that measure measures the total length of color . The opposite is also true: measure splitting can be solved by continuous splitting, using a more sophisticated reduction.[1]:252–253
Proof
[编辑]時的情況可以用博蘇克烏蘭定理證明[2]。當是其他質數,也可以用推廣了的該定理證明[3]。
而是合成數時, the proof is as follows (demonstrated for the measure-splitting variant). Suppose . There are measures, each of which values the entire necklace as . Using cuts, divide the necklace to parts such that measure of each part is exactly . Using cuts, divide each part to parts such that measure of each part is exactly . All in all, there are now parts such that measure of each part is exactly . The total number of cuts is plus which is exactly .
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[4] 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 D1 and D2 of { 1, 2, ..., t }, not both empty, such that , a (t − 1)-split exists such that:
- If colour , then partition 1 has more beads of colour i than partition 2;
- If colour , 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 D1 and D2, not both empty, there exists a (t − 1)-split so that thief 1 gets more beads of types in his preference set D1 than thief 2; thief 2 gets more beads of types in her preference set D2 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 D1 consist of the fictitious colour and D2 empty. Then Simonyi's result shows that there is a t-split with equal numbers of each real colour.
Negative result
[编辑]For every there is a measurable -coloring of the real line such that no interval can be fairly split using at most cuts.[5]
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.[6]
Approximation algorithm
[编辑]An approximation algorithm for splitting a necklace can be derived from an algorithm for consensus halving.[7]
參見
[编辑]參考資料
[编辑]- ^ 1.0 1.1 1.2 1.3 1.4 1.5 Alon, Noga. Splitting Necklaces. Advances in Mathematics. 1987, 63 (3): 247–253. doi:10.1016/0001-8708(87)90055-7
.
- ^ 2.0 2.1 Alon, Noga; West, D. B. The Borsuk-Ulam theorem and bisection of necklaces. Proceedings of the American Mathematical Society. December 1986, 98 (4): 623–628. doi:10.1090/s0002-9939-1986-0861764-9
.
- ^ I.Barany and S.B.Shlosman and A.Szucs. On a topological generalization of a theorem of Tverberg (PDF). Journal of the London Mathematical Society. 1981, 2 (23): 158–164. CiteSeerX 10.1.1.640.1540
. doi:10.1112/jlms/s2-23.1.158.
- ^ Simonyi, Gábor. Necklace bisection with one cut less than needed. Electronic Journal of Combinatorics. 2008, 15 (N16). doi:10.37236/891
.
- ^ Alon, Noga. Splitting necklaces and measurable colorings of the real line. Proceedings of the American Mathematical Society. November 25, 2008, 137 (5): 1593–1599. ISSN 1088-6826. arXiv:1412.7996
. doi:10.1090/s0002-9939-08-09699-8.
- ^ de Longueville, Mark; Rade T. Živaljević. Splitting multidimensional necklaces. Advances in Mathematics. 2008, 218 (3): 926–939. arXiv:math/0610800
. doi:10.1016/j.aim.2008.02.003.
- ^ Simmons, Forest W.; Su, Francis Edward. Consensus-halving via theorems of Borsuk-Ulam and Tucker. Mathematical Social Sciences. February 2003, 45 (1): 15–25. CiteSeerX 10.1.1.203.1189
. doi:10.1016/s0165-4896(02)00087-2.
外部鏈接
[编辑]- YouTube上的"Sneaky Topology", an introductory video presenting the problem with its topological solution.