Kaulakorun leikkaus ongelma

Kaulakorun leikkausongelma on kombinatoriikan ja mittateorian ongelmasarjan nimi . Ongelman muotoili ja ratkaisi matemaatikot Noga Alon [1] ja Douglas B. West [2] .

Perusehdot määrittelevät kaulakorun , jossa on erivärisiä helmiä. Kaulakoru tulee jakaa useiden osallistujien tai varkaiden kesken (usein oletetaan, että kaulakoru on varastettu), jotta jokainen osallistuja saisi tietyn määrän helmiä kutakin väriä. Lisäksi leikkauksia tulee tehdä mahdollisimman vähän (jotta helmiä yhdistävässä ketjussa häviäisi mahdollisimman vähän metallia).

Muunnelmia

Seuraavat ongelman versiot ratkaistiin alkuperäisessä artikkelissa:

Diskreetti leikkaus [3] : Kaulakorussa on helmiä. Helmiä on eri värejä. Jokaisen värin helmiä on , jossa on positiivinen kokonaisluku. Sinun tulee leikata kaulakoru osiin (ei välttämättä jatkuviin), joista jokaisessa on täsmälleen i -värisiä helmiä . Leikkauksia ei tule käyttää enempää . Huomaa, että jos jokaisen värin helmet asettuvat kaulakoruun jatkuvasti, tarvitset jokaisen värin sisälle vähintään leikkauksia, jotta arvo on optimaalinen. $k\cdot n$ $t$ ${\displaystyle k\cdot a_{i))$ $i$ $a_{i}$ $k$ $a_{i}$ ${\näyttötyyli (k-1)t}$ $k-1$ ${\näyttötyyli (k-1)t}$
Jatkuva leikkaus [4] : Kaulakoru on todellinen segmentti . Jokainen segmentin piste on väritetty jollakin väreistä. Minkä tahansa värin kohdalla värillä värjätty pistejoukko on Lebesgue-mitattavissa ja sillä on pituus , jossa on ei-negatiivinen reaaliluku. Sinun tulee jakaa segmentti osiin (ei välttämättä jatkuviin), jotta jokaisessa osassa värin kokonaispituus on täsmälleen yhtä suuri kuin . Älä käytä enempää leikkauksia. $[0,k\cdot n]$ $t$ $i$ $minä,$ ${\displaystyle k\cdot a_{i))$ $a_{i}$ $k$ $i$ $a_{i}$ ${\näyttötyyli (k-1)t}$
Jako mitalla [5] : Kaulakoru on todellinen segmentti. Segmentillä on erilaisia mittoja, jotka kaikki ovat pituudeltaan ehdottoman jatkuvia. Koko kaulakorun mitta on . Segmentti tulee jakaa osiin (ei välttämättä jatkuviin), jotta jokaisen mittaosan mitta on täsmälleen yhtä suuri kuin . Älä käytä enempää leikkauksia. Tämä on yleistys Hobby-Rice-lauseesta ja sitä käytetään kakun tarkan jaon saamiseksi . $t$ $i$ ${\displaystyle k\cdot a_{i))$ $k$ $i$ $a_{i}$ ${\näyttötyyli (k-1)t}$

Jokainen tehtävä voidaan ratkaista seuraavalla tavalla:

Diskreetti leikkaus voidaan ratkaista jatkuvalla leikkauksella, koska erillinen kaulakoru voidaan pelkistää todelliseksi viivavärjäytykseksi , jossa jokainen pituus 1 on värjätty vastaavan helmen värillä. Siinä tapauksessa, että jatkuva väliseinä yrittää leikata vanteen sisällä, leikkausta voidaan siirtää siten, että leikkaukset ovat vain helmien välissä [6] . $[0,k\cdot n]$
Jatkuva leikkaus voidaan tehdä jakamalla mitalla, koska segmentin värjäys väreissä voidaan muuttaa mittajoukoksi siten, että mitta heijastaa värin pituutta . Päinvastoin on myös totta - mittojen mukaan jakautuminen voidaan saada jatkuvalla leikkaamalla hienomman pienennyksen avulla [7] . $t$ $t$ $i$ $i$

Todiste

Tapaus voidaan todistaa Borsuk-Ulam-lauseella [2] . $k = 2$

Jos on pariton alkuluku , todistuksessa käytetään Borsuk-Ulam -lauseen yleistystä [8] . $k$

Jos on yhdistetty , todistus on seuraava (esittelemme jakamisen mitan mukaan). Oletetaan, että . On toimenpiteitä, joista jokainen arvioi koko kaulakorun . Leikkausten avulla jaamme kaulakorun osiin niin, että kunkin osan mitta on täsmälleen yhtä suuri kuin . Leikkaa jokainen osa osiin avulla , jotta kunkin osan mitta on täsmälleen yhtä suuri kuin . Nyt on sellaisia osia, että kunkin osan mitta on täsmälleen . Leikkausten kokonaismäärä on , mikä on täsmälleen . $k$ $k=p\cdot q$ $t$ ${\displaystyle p\cdot q\cdot a_{i))$ ${\näyttötyyli (p-1)\cdot t}$ $s$ $i$ $q\cdot a_{i}$ $(q-1)\cdot t$ $q$ $i$ $a_{i}$ $pq$ $i$ $a_{i}$ ${\näyttötyyli (p-1)\cdot t+p(q-1)\cdot t}$ $(pq-1)\cdot t$

Lisää tuloksia

Yksi leikkaus vähemmän kuin tarvitaan

Kahden varkaan [eli k = 2] ja t värin tapauksessa reilu leikkaus vaatisi enintään t leikkauksen. Jos kuitenkin vain leikkaukset ovat sallittuja, unkarilainen matemaatikko Gábor Szymonyi [9] osoitti, että kaksi varasta voi saavuttaa melkein oikeudenmukaisen jaon seuraavassa mielessä: $t-1$

jos helmet kaulakorussa on järjestetty siten, että t - leikkaus on mahdollista, niin kahdelle osajoukolle D 1 ja D 2 sarjoista , jotka kumpikaan eivät ole tyhjiä siten, että , on -leikkaus, joka: $\{1,2,\dots ,t\}$ $D_{1}\cap D_{2}=\varnothing$ ${\näyttötyyli (t-1)}$

Jos väri on , osassa 1 on enemmän helmiä väriä i kuin osassa 2; $i\in D_{1}$
Jos väri on , osassa 2 on enemmän helmiä väriä i kuin osassa 1; $i\in D_{2}$
Jos väri i ei kuulu mihinkään osiin ja , molemmissa osissa on sama määrä i -värin helmiä . $D_{1}$ $D_{2}$

Tämä tarkoittaa, että jos varkailla on mieltymykset kahdessa "preferenssijoukossa" D 1 ja D 2 , joista ainakin yksi ei ole tyhjä, on olemassa -osio siten, että varas 1 saa enemmän helmiä mieltymysjoukostaan D 1 kuin varas 2, varas 2 saa enemmän helmiä suosikkisarjastaan D 2 kuin varas 1, ja loput ovat samat. ${\näyttötyyli (t-1)}$

Simony kiittää Gabor Tardosta huomautuksella, että yllä oleva tulos on suora yleistys Alonin alkuperäisestä kaulakorulauseesta tapauksessa k = 2. Joko kaulakorussa on -leikkaus tai ei. Jos on, niin ei ole mitään todistettavaa. Jos ei, voimme lisätä kaulakoruun yhden fiktiivisen värihelmen ja muodostaa kaksi sarjaa, sarja D 1 koostuu tästä fiktiivisestä väristä ja sarja D 2 on tyhjä. Simonyn tulos osoittaa, että on olemassa t -leikkaus, jossa on yhtä monta väriä jokaisesta oikeasta väristä. ${\näyttötyyli (t-1)}$

Negatiivinen tulos

Jokaiselle viivalle on olemassa mitattavissa oleva väritys todellisen viivan väreissä siten, että mitään väliä ei voida jakaa reilusti enintään leikkauksilla [10] . $k\geqslant 1$ ${\näyttötyyli (k+3)}$ $k$

Moniulotteisen kaulakorun leikkaaminen

Tulos voidaan laajentaa todennäköisyysmittauksiin n , jotka on määritelty d -ulotteisessa kuutiossa millä tahansa k - varkaiden sivujen suuntaisten hypertasojen yhdistelmällä [11] . $n(k-1)$

Approksimaatioalgoritmi

Approksimaatioalgoritmi kaulakorun leikkaamiseksi voidaan johtaa johdonmukaisen puolittamisen algoritmista [12] .

Katso myös

Muistiinpanot

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

Kirjallisuus

Noga Alon. Kaulakorujen halkaisu // Matematiikan edistysaskel. - 1987. - T. 63 , no. 3 . - doi : 10.1016/0001-8708(87)90055-7 .
Noga Alon, West DB Borsuk-Ulam-lause ja kaulakorujen puolittaminen // Proceedings of the American Mathematical Society. - 1986. - joulukuu ( nide 98 , numero 4 ). - doi : 10.1090/s0002-9939-1986-0861764-9 .
I. Barany, S. B. Shlosman, A. Szucs. Tverbergin lauseen topologisesta yleistyksestä // Journal of the London Mathematical Society. - 1981. - Vol. 2 , numero. 23 . - doi : 10.1112/jlms/s2-23.1.158 .
Gabor Simonyi. Kaulakorun puolittaminen yhdellä leikkauksella kuin tarvitaan // Electronic Journal of Combinatorics. - 2008. - T. 15 , no. N16 .
Noga Alon. Halkaisevat kaulakorut ja todellisen linjan mitattavissa olevat värit // Proceedings of the American Mathematical Society. - 2008. - marraskuu ( nide 137 , numero 5 ). — ISSN 1088-6826 . - doi : 10.1090/s0002-9939-08-09699-8 . - arXiv : 1412.7996 .
Mark de Longueville, Rade T. Zivaljević. Moniulotteisten kaulakorujen halkaisu // Matematiikan edistysaskel. - 2008. - T. 218 , no. 3 . - doi : 10.1016/j.aim.2008.02.003 . - arXiv : math/0610800 .
Forest W. Simmons, Francis Edward Su. Konsensuksen puolittaminen Borsuk-Ulamin ja Tuckerin lauseiden kautta // Mathematical Social Sciences. - 2003. - Helmikuu ( nide 45 , numero 1 ). - doi : 10.1016/s0165-4896(02)00087-2 .

Linkit

" Sneaky Topology" YouTubessa .