Nyaklánc vágási probléma

A nyakláncvágási probléma a kombinatorika és a mértékelmélet problémasorozatának a neve . A problémát Noga Alon [1] és Douglas B. West [2] matematikusok fogalmazták meg és oldották meg .

Az alapvető feltételek határozzák meg a különböző színű gyöngyökkel ellátott nyakláncot . A nyakláncot fel kell osztani több résztvevő vagy tolvaj között (gyakran azt feltételezik, hogy a nyakláncot ellopták), hogy minden résztvevő bizonyos számú gyöngyöt kapjon minden színből. Ezenkívül a vágások száma a lehető legkevesebb legyen (annak érdekében, hogy a lehető legkevesebb fémet veszítse el a gyöngyöket összekötő láncban).

Változatok

A probléma következő változatait oldották meg az eredeti cikkben:

Diszkrét vágás [3] : A nyakláncon gyöngyök találhatók. A gyöngyök különböző színűek. Minden színből vannak gyöngyök , ahol egy pozitív egész szám. Vágja a nyakláncot részekre (nem feltétlenül folyamatos), amelyek mindegyikén pontosan i színű gyöngyök találhatók . Nem szabad több vágást használni. Vegye figyelembe, hogy ha az egyes színek gyöngyei folyamatosan vannak elrendezve a nyakláncon, akkor minden színben legalább vágások szükségesek, hogy az érték optimális legyen. $k\cdot n$ $t$ $k\cdot a_{i}$ $én$ $a_{i}$ $k$ $a_{i}$ $(k-1)t$ $k-1$ $(k-1)t$
Folyamatos vágás [4] : A nyaklánc egy igazi szegmens . A szegmens minden pontja valamelyik színnel van színezve . Bármilyen szín esetén a színnel színezett pontok halmaza Lebesgue mérhető , és hossza , ahol egy nem negatív valós szám. A szegmenst részekre kell bontani (nem feltétlenül folytonos), hogy minden részben a szín teljes hossza pontosan egyenlő legyen a -val . Ne használjon több vágást. $[0,k\cdot n]$ $t$ $én$ $én,$ $k\cdot a_{i}$ $a_{i}$ $k$ $én$ $a_{i}$ $(k-1)t$
Felosztás mérték szerint [5] : A nyaklánc valódi szegmens. Különféle mértékek vannak egy szegmensen, amelyek mindegyike abszolút folyamatos. Az egész nyaklánc mértéke mértékben . A szakaszt részekre kell osztani (nem feltétlenül folytonos), hogy az egyes mértékrészek mértéke pontosan egyenlő legyen a -val . Ne használjon több vágást. Ez a Hobby-Rice tétel általánosítása, és a torta pontos felosztására szolgál . $t$ $én$ $k\cdot a_{i}$ $k$ $én$ $a_{i}$ $(k-1)t$

Minden feladat a következő módon oldható meg:

A diszkrét vágás megoldható folyamatos vágással, hiszen egy diszkrét nyaklánc valós vonalszínezéssé redukálható, amelyben minden 1 hosszúságú vonalszakasz a megfelelő gyöngy színével színezhető. Abban az esetben, ha egy folytonos válaszfal egy gyöngy belsejében próbál vágni, a vágást el lehet tolni úgy, hogy a vágások csak a gyöngyök között legyenek [6] . $[0,k\cdot n]$
A folyamatos vágás elvégezhető mérték szerinti particionálással, mivel egy szegmens színezése mértékegységgé alakítható , így a mérték tükrözi a szín hosszát . Ennek a fordítottja is igaz - a finomabb redukció segítségével folyamatos vágással mértékenkénti felosztás érhető el [7] . $t$ $t$ $én$ $én$

Bizonyítás

Az eset a Borsuk-Ulam tétellel igazolható [ 2] . $k=2$

Ha páratlan prím , akkor a bizonyítás a Borsuk-Ulam tétel [8] általánosítását használja . $k$

Ha összetett , akkor a bizonyítás a következő lesz (bemutatjuk a mérték szerinti felosztás lehetőségét). Tegyük fel, hogy . Vannak olyan intézkedések, amelyek mindegyike a teljes nyakláncot értékeli . Vágások segítségével részekre osztjuk a nyakláncot úgy, hogy az egyes részek mérete pontosan egyenlő legyen a -val . Vágjuk az egyes részeket a segítségével részekre úgy, hogy az egyes részek mértéke pontosan egyenlő legyen -vel . Mostantól vannak olyan részek, amelyek mindegyikének mértéke pontosan . A vágások teljes száma , ami pontosan . $k$ $k=p\cdot q$ $t$ ${\displaystyle p\cdot q\cdot a_{i))$ ${\megjelenítési stílus (p-1)\cdot t}$ $p$ $én$ $q\cdot a_{i}$ $(q-1)\cdot t$ $q$ $én$ $a_{i}$ $pq$ $én$ $a_{i}$ ${\megjelenítési stílus (p-1)\cdot t+p(q-1)\cdot t}$ $(pq-1)\cdot t$

További eredmények

Egy vágással kevesebb a szükségesnél

Két tolvaj [azaz k = 2] és t szín esetén a tisztességes vágás legfeljebb t vágást igényelne . Ha azonban csak vágás engedélyezett, Szymonyi Gábor [9] magyar matematikus megmutatta, hogy két tolvaj a következő értelemben szinte igazságos felosztást tud elérni: $t-1$

ha a gyöngyök a nyakláncon úgy vannak elrendezve, hogy lehetséges a t -vágás, akkor a halmazok két D 1 és D 2 részhalmazára , amelyek nem üresek úgy, hogy , van egy -vágás, amely: $\{1,2,\dots ,t\}$ $D_{1}\cap D_{2}=\varnothing$ ${\megjelenítési stílus (t-1)}$

Ha a szín , akkor az 1. rész több i színű gyöngyöt tartalmaz, mint a 2. rész; $i\in D_{1}$
Ha a szín , akkor a 2. rész több i színű gyöngyöt tartalmaz, mint az 1. rész; $i\in D_{2}$
Ha az i szín nem tartozik egyik és részhez sem, mindkét részen ugyanannyi i színű gyöngy van . $D_{1}$ $D_{2}$

Ez azt jelenti, hogy ha a tolvajoknak két D 1 és D 2 "preferencia" halmaza van , amelyek közül legalább az egyik nem üres, akkor létezik egy -partíció, így az 1. tolvaj több gyöngyöt kap a D preferenciakészletéből. 1 , mint a tolvaj 2, a tolvaj 2 több gyöngyöt kap a D 2 preferenciakészletéből, mint a tolvaj 1, és a maradék ugyanannyi lesz. ${\megjelenítési stílus (t-1)}$

Simony Tardos Gábornak tulajdonítja azt a megjegyzést, hogy a fenti eredmény Alon eredeti nyaklánctételének direkt általánosítása k = 2 esetben. Vagy van -vágás a nyakláncon, vagy nincs. Ha igen, nincs mit bizonyítani. Ha nem, akkor hozzáadhatunk egy fiktív színű gyöngyöt a nyaklánchoz, és két készletet alkothatunk, a D 1 készlet ebből a fiktív színből áll, a D 2 készlet pedig üres. Simony eredménye azt mutatja, hogy létezik egy t - vágás minden valódi színből azonos számú színnel. ${\megjelenítési stílus (t-1)}$

Negatív eredmény

Bármelyik esetén létezik egy mérhető színezés a valódi vonal színeiben, így egyetlen intervallum sem osztható fel tisztességesen legfeljebb vágással [10] . $k\geqslant 1$ ${\megjelenítési stílus (k+3)}$ $k$

A többdimenziós nyaklánc vágása

Az eredmény kiterjeszthető egy d -dimenziós kockán definiált n valószínűségi mérőszámokra k tolvajok oldalaival párhuzamos hipersíkok tetszőleges kombinációjával [11] . $n(k-1)$

Közelítő algoritmus

A nyaklánc vágására szolgáló közelítő algoritmus a következetes felezés algoritmusából származtatható [12] .

Lásd még

Jegyzetek

↑ Egyedül, 1987 , p. 247-253.
↑ 1 2 Alon, West, 1986 , p. 623-628.
↑ Egyedül, 1987 , p. 247–253 Th 1.1.
↑ Egyedül, 1987 , p. 247–253 Th 2.1.
↑ Egyedül, 1987 , p. 247–253 Th 1.2.
↑ Egyedül, 1987 , p. 249.
↑ Egyedül, 1987 , p. 252-253.
↑ Barany, Shlosman, Szucs, 1981 , p. 158–164.
↑ Simonyi, 2008 .
↑ Egyedül, 2008 , p. 1593–1599
↑ de Longueville, Živaljević, 2008 , p. 926-939.
↑ Simmons, Su, 2003 , p. 15–25.

Irodalom

Noga Alon. Splitting Necklaces // Előrelépések a matematikában. - 1987. - T. 63 , sz. 3 . - doi : 10.1016/0001-8708(87)90055-7 .
Noga Alon, West DB A Borsuk-Ulam tétel és a nyakláncok felezése // Proceedings of the American Mathematical Society. - 1986. - December ( 98. évf. , 4. szám ). - doi : 10.1090/s0002-9939-1986-0861764-9 .
I. Barany, S. B. Shlosman, A. Szucs. Egy tverbergi tétel topológiai általánosításáról // Journal of the London Mathematical Society. - 1981. - 2. kötet , szám. 23 . - doi : 10.1112/jlms/s2-23.1.158 .
Simonyi Gábor. Nyaklánc felezése a szükségesnél eggyel kevesebb vágással // Electronic Journal of Combinatorics. - 2008. - T. 15 , sz. N16 .
Noga Alon. Hasító nyakláncok és a valódi vonal mérhető színezése // Proceedings of the American Mathematical Society. - 2008. - november ( 137. évf. , 5. szám ). — ISSN 1088-6826 . - doi : 10.1090/s0002-9939-08-09699-8 . - arXiv : 1412.7996 .
Mark de Longueville, Rade T. Zivaljević. Többdimenziós nyakláncok felosztása // Előrelépések a matematikában. - 2008. - T. 218 , sz. 3 . - doi : 10.1016/j.aim.2008.02.003 . - arXiv : math/0610800 .
Forest W. Simmons, Francis Edward Su. Konszenzus-felezés Borsuk-Ulam és Tucker tételein keresztül // Mathematical Social Sciences. - 2003. - február ( 45. évf. , 1. szám ). - doi : 10.1016/s0165-4896(02)00087-2 .

Linkek

"Sneaky Topology" a YouTube -on .