Problem med at klippe halskæde

Halskædeskæringsproblemet er navnet på en række problemer fra kombinatorik og målteori . Problemet blev formuleret og løst af matematikerne Noga Alon [1] og Douglas B. West [2] .

Grundlæggende betingelser definerer en halskæde med perler i forskellige farver. Halskæden bør deles mellem flere deltagere eller tyve (det antages ofte, at halskæden er stjålet), således at hver deltager ville modtage et vist antal perler af hver farve. Desuden skal antallet af snit være så få som muligt (for at miste så lidt metal som muligt i kæden, der forbinder perlerne).

Variationer

Følgende varianter af problemet blev løst i den originale artikel:

Diskret udskæring [3] : Halskæden har perler. Perlerne er i forskellige farver. Der er perler af hver farve , hvor er et positivt heltal. Du bør skære halskæden i dele (ikke nødvendigvis kontinuerlige), som hver især har nøjagtige perler af farve i . Der må ikke bruges flere udskæringer. Bemærk, at hvis perlerne i hver farve er arrangeret kontinuerligt på halskæden, så skal du som minimum snit inde i hver farve, så værdien er optimal. $k\cdot n$ $t$ $k\cdot a_{i}$ $jeg$ $a_{i}$ $k$ $a_{i}$ $(k-1)t$ $k-1$ $(k-1)t$
Kontinuerlig skæring [4] : Halskæden er et rigtigt segment . Hvert punkt i segmentet er farvet i en af farverne. For enhver farve er sæt af punkter farvet efter farve Lebesgue-målbar og har længde , hvor er et ikke-negativt reelt tal. Du bør bryde segmentet op i dele (ikke nødvendigvis kontinuerlige), så den samlede længde af farven i hver del er nøjagtigt lig med . Brug ikke flere snit. $[0,k\cdot n]$ $t$ $jeg$ $jeg,$ $k\cdot a_{i}$ $a_{i}$ $k$ $jeg$ $a_{i}$ $(k-1)t$
Opdeling efter mål [5] : Halskæden er et rigtigt segment. Der er forskellige mål på et segment, alle absolut kontinuerlige i længden. Mål på hele halskæden i mål er . Segmentet bør opdeles i dele (ikke nødvendigvis kontinuert), så målet for hver del i mål er nøjagtigt lig med . Brug ikke flere snit. Dette er en generalisering af Hobby-Rice-sætningen og bruges til at opnå en nøjagtig opdeling af kagen . $t$ $jeg$ $k\cdot a_{i}$ $k$ $jeg$ $a_{i}$ $(k-1)t$

Hver opgave kan løses på følgende måde:

Et diskret snit kan løses ved et kontinuerligt snit, da en diskret halskæde kan reduceres til en ægte linjefarvning , hvor hvert linjesegment af længde 1 er farvet af farven på den tilsvarende perle. I det tilfælde, hvor en kontinuerlig skillevæg forsøger at skære inde i en vulst, kan snittet forskydes, så snittene kun er mellem perlerne [6] . $[0,k\cdot n]$
Kontinuerlig skæring kan udføres ved at opdele efter mål, da farvningen af et segment i farver kan omdannes til et sæt mål, så målet afspejler længden af farven . Det omvendte er også tilfældet - en opdeling efter mål kan opnås ved kontinuerlig skæring ved hjælp af finere reduktion [7] . $t$ $t$ $jeg$ $jeg$

Bevis

Sagen kan bevises ved Borsuk-Ulam-sætningen [2] . $k=2$

Hvis er et ulige primtal , bruger beviset en generalisering af Borsuk-Ulam-sætningen [8] . $k$

Hvis er sammensat , vil beviset være som følger (vi demonstrerer for muligheden for at opdele efter mål). Lad os antage det . Der er mål, som hver især vurderer hele halskæden som . Ved hjælp af udskæringer deler vi halskæden op i dele, så målet på hver del er nøjagtigt lig med . Lad os skære hver del i dele med hjælp , så målet for hver del er nøjagtigt lig med . Der er nu dele sådan, at målet for hver del er nøjagtigt . Det samlede antal klip er , hvilket er præcis . $k$ $k=p\cdot q$ $t$ ${\displaystyle p\cdot q\cdot a_{i))$ $(p-1)\cdot t$ $s$ $jeg$ $q\cdot a_{i}$ $(q-1)\cdot t$ $q$ $jeg$ $a_{i}$ $pq$ $jeg$ $a_{i}$ $(p-1)\cdot t+p(q-1)\cdot t$ $(pq-1)\cdot t$

Yderligere resultater

Et snit mindre end nødvendigt

I tilfælde af to tyve [dvs. k = 2] og t- farver, ville et retfærdigt snit højst kræve t snit. Hvis der dog kun er snit tilladt, viste den ungarske matematiker Gábor Szymonyi [9] , at to tyve kan opnå en næsten retfærdig opdeling i følgende forstand: $t-1$

hvis perlerne på halskæden er arrangeret på en sådan måde, at et t - snit er muligt, så for to undersæt D 1 og D 2 af sættene , som begge ikke er tomme , således at der er et -snit, således at: $\{1,2,\dots ,t\}$ $D_{1}\cap D_{2}=\varnothing$ $(t-1)$

Hvis farve er , så har del 1 flere perler af farve i end del 2; $i\in D_{1}$
Hvis farve er , så har del 2 flere perler af farve i end del 1; $i\in D_{2}$
Hvis farve i ikke hører til nogen af delene og , har begge dele det samme antal farveperler i . $D_{1}$ $D_{2}$

Det betyder, at hvis tyvene har præferencer i form af to sæt "præferencer" D 1 og D 2 , hvoraf mindst det ene er ikke-tomt, eksisterer der en -partition, således at tyven 1 får flere perler fra sit præferencesæt D 1 end tyv 2, tyv 2 vil få flere perler fra sit præferencesæt D 2 end tyv 1, og resten vil være den samme. $(t-1)$

Simony krediterer Gabor Tardos med den bemærkning, at ovenstående resultat er en direkte generalisering af Alons oprindelige halskædesætning i tilfældet k = 2. Enten har halskæden et -snit, eller også har den ikke. Hvis det er tilfældet, er der intet at bevise. Hvis ikke, kan vi tilføje en fiktiv farveperle til halskæden og danne to sæt, sættet D 1 består af denne fiktive farve, og sættet D 2 er tomt. Simonys resultat viser, at der er et t - snit med lige mange farver af hver rigtig farve. $(t-1)$

Negativt resultat

For enhver , eksisterer der en målbar farvning i farverne på den rigtige linje, således at intet interval retfærdigt kan opdeles ved højst snit [10] . $k\geqslant 1$ $(k+3)$ $k$

Skæring af den multidimensionelle halskæde

Resultatet kan udvides til sandsynlighedsmål n defineret på en d - dimensionel terning med en hvilken som helst kombination af hyperplaner parallelt med siderne for k tyve [11] . $n(k-1)$

Approksimationsalgoritme

En tilnærmelsesalgoritme til at skære halskæden kan udledes af algoritmen for konsekvent halvering [12] .

Se også

Noter

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

Litteratur

Noga Alon. Opdele halskæder // Fremskridt i matematik. - 1987. - T. 63 , no. 3 . - doi : 10.1016/0001-8708(87)90055-7 .
Noga Alon, West DB Borsuk-Ulam-sætningen og halvering af halskæder // Proceedings of the American Mathematical Society. - 1986. - December ( bind 98 , hæfte 4 ). - doi : 10.1090/s0002-9939-1986-0861764-9 .
I. Barany, S.B. Shlosman, A. Szucs. Om en topologisk generalisering af et teorem fra Tverberg // Journal of the London Mathematical Society. - 1981. - Bind 2 , udgave. 23 . - doi : 10.1112/jlms/s2-23.1.158 .
Gabor Simonyi. Halskædehalvering med et snit mindre end nødvendigt // Electronic Journal of Combinatorics. - 2008. - T. 15 , no. N16 .
Noga Alon. Splittende halskæder og målbare farver af den rigtige linje // Proceedings of the American Mathematical Society. - 2008. - November ( bind 137 , hæfte 5 ). — ISSN 1088-6826 . - doi : 10.1090/s0002-9939-08-09699-8 . - arXiv : 1412.7996 .
Mark de Longueville, Rade T. Zivaljević. Opdeling af multidimensionelle halskæder // Fremskridt i matematik. - 2008. - T. 218 , no. 3 . - doi : 10.1016/j.aim.2008.02.003 . - arXiv : math/0610800 .
Forest W. Simmons, Francis Edward Su. Konsensus-halvering via teoremer fra Borsuk-Ulam og Tucker // Mathematical Social Sciences. - 2003. - Februar ( bind 45 , hæfte 1 ). - doi : 10.1016/s0165-4896(02)00087-2 .