Sandwich-lause

Sandwich -lause sanoo, että kun n - ulotteisessa euklidisessa avaruudessa on n mitattavissa olevaa "objektia" , ne voidaan puolittaa ( mittansa eli tilavuuden mukaan) yhdellä ( n − 1) -ulotteisella hypertasolla .

Väite tehtiin Hugo Steinhausin toimesta ja sen todisti Stefan Banach (kolmas ulottuvuudessa, ei olettaen lauseen automaattista laajenemista n-ulotteiseen tapaukseen), ja vuotta myöhemmin väitettä kutsuttiin Stone-Tukey-lauseeksi Arthur G.:n mukaan. Stone ja John Tukey .

Otsikko

Voileipälause on saanut nimensä tapauksesta, jossa n = 3 ja kolme minkä tahansa muotoista kohdetta ovat kinkkuviipale ja kaksi leipää . Suhteellisesti sanottuna voileipä , joka voidaan jakaa samanaikaisesti yhdellä leikkauksella (eli tasolla ). Dimensiossa kaksi lause tunnetaan pannukakkulauseena , koska se koostuu äärettömän ohuen pannukakun leikkaamisesta kahteen puolikkaaseen yhdellä leikkauksella (eli suoralla viivalla ).

Historia

Bayerin ja Szardeckin [1] mukaan varhaisin paperi sandwich-lauseesta, nimittäin tapaukselle, jossa n = 3 leikkausta kolmesta kappaleesta tasossa, on Steinhausin paperi [2] . Bayerin ja Szzardeckin artikkeli sisältää käännöksen vuoden 1938 artikkelista. Artikkelissa sanotaan ongelman väittämän Hugo Steinhausin ansioksi ja väitetään, että Stefan Banach oli ensimmäinen, joka ratkaisi ongelman pelkistämällä Borsuk-Ulam-lauseen . Artikkeli esittelee ongelman kahdella tavalla. Ensimmäinen on muodollinen: "Onko aina mahdollista jakaa kolme mielivaltaisesti sijoitettua kappaletta yhdellä tasolla?". Toinen, epävirallinen: "Voimmeko laittaa kinkunpalan veitsen alle niin, että liha, luu ja rasva jakautuvat veitsellä kahtia?" Artikkeli tarjosi todisteen lauseesta.

Uudempi artikkeli on Stonen ja Tukeyn [3] paperi , joka antoi nimensä "Stone-Tukey-lauseelle". Tämä artikkeli todistaa lauseen n - ulotteisen version yleisemmissä mittaolosuhteissa. Artikkelissa katsotaan tapauksen n = 3 ansioksi Stanisław Ulamin omien tietojensa perusteella, mutta Bayer ja Zzardecki [1] väittävät, että tämä on väärä, viitaten Steinhausin kirjoitukseen, vaikka he väittävät: "Ulam antoi perustavanlaatuisen panoksen " Borsuk-Ulam-lause ".

Kaksiulotteinen versio: todiste "liikkuvalla veitsellä"

Lauseen kaksiulotteinen versio (tunnetaan myös nimellä pannukakkulause ) voidaan todistaa argumenteilla, jotka esiintyvät kirjallisuudessa reilun kakun leikkaamisen ongelmasta (katso esimerkiksi Robertson-Webbin Moving Knife Procedure ).

Millä tahansa kulmalla voimme leikata pannukakun nro 1 suoralla linjalla kulmassa (nähdäksesi tämän siirrämme suoraa kulmassa kohdasta - . Pannukakun nro 1 osa, joka on leikattu suoralla viivalla, muuttuu jatkuvasti 0:sta 1:een, joten välilauseen arvon mukaan sen on otettava arvo 1/2 jonnekin). $\alpha \in [0,180^{\circ }]$ $\alpha$ $\alpha$ $-\infty$ $\infty$

Tämä tarkoittaa, että voimme ottaa suoran veitsen ja kiertää sitä kulman läpi , liikuttamalla sitä yhdensuuntaisesti vaaditun etäisyyden kanssa niin, että pannukakku #1 leikataan aina puoliksi missä tahansa kulmassa. $\alpha \in [0,180^{\circ }]$

Kun veitsi on 0:n kulmassa, se leikkaa myös pannukakun nro 2, mutta sen osat eivät välttämättä ole yhtä suuret (jos olimme onnekkaita ja palat olivat yhtä suuret, teimme työmme). Määritellään se veitsen "positiiviseksi" puolelle, jolla pannukakun nro 2 osuus on suurempi. Määrittelemme sen pannukakun nro 2 osuudeksi veitsen positiivisella puolella. Aluksi . $p(\alpha )$ $p(0)\geqslant 1/2$

Kun veitsi kääntyy 180, se on samassa paikassa, mutta ylösalaisin, joten . Väliarvolauseen mukaan täytyy olla kulma, jossa . Tällä teräkulmalla leikkaaminen leikkaa molemmat pannukakut kahtia samanaikaisesti. $p(180)\leqslant 1/2$ $p(\alpha )=1/2$

n -ulotteinen versio: todistus käyttäen Borsuk-Ulam-lausetta

Sandwich-lause voidaan todistaa seuraavasti käyttämällä Borsuk-Ulam -lausetta . Annettu todistus seuraa Steinhausin et al.:n vuoden 1938 julkaisussa esittämää todistusta, jonka syynä on Stefan Banach tapaukselle n =3 . Ekvivaranttitopologian alalla tämä todistus vastaa konfiguraatioavaruuden/testauksen avaruuskartan paradigmaa.

Merkitään n kohdetta , jotka haluamme jakaa kahteen yhtä aikaa. Olkoon S yksikkö ( n − 1) -pallo , joka on upotettu n - ulotteiseen euklidiseen avaruuteen ja jonka keskipiste on origossa . Jokaiselle pallon S pinnalla olevalle pisteelle p voidaan määrittää jatkumo orientoituneista affiineista hypertasoista (ei välttämättä keskuksen 0 läpi), jotka ovat kohtisuorassa ( normaali ) vektoriin nähden origosta kohdassa p , "positiivisella" sivu" kunkin hypertason, joka on määritelty sivuksi, johon vektori osoittaa (eli se on suuntauksen valinta ). Väliarvolauseen lauseen mukaan mikä tahansa tällaisten hypertasojen perhe sisältää vähintään yhden hypertason, joka puolittaa rajatun kohteen - yhdellä äärimmäisellä käännöksellä ei ole tilavuutta y positiivisella puolella, mutta äärimmäisellä käännöksellä toiseen suuntaan , koko volyymi on positiivisella puolella , joten näiden ääriarvojen välillä on oltava siirto, jonka tilavuudesta on puolet positiivisella puolella . Jos tällaisia hypertasoja on useampi kuin yksi, voimme valita yhden puolitusvälin keskipisteeksi . Siten jokaiselle pallon S pisteelle p saadaan hypertaso , joka on kohtisuorassa origosta pisteeseen p olevaan vektoriin ja joka puolittaa . ${\displaystyle A_{1},A_{2},\dots ,A_{n))$ $\mathbb {R} ^{n}$ $A_{n}$ $A_{n}$ $A_{n}$ $A_{n}$ ${\näyttötyyli \pi (p)}$ $A_{n}$

Määritämme nyt funktion f ( n − 1) -pallosta S ( n − 1) -ulotteisessa euklidisessa avaruudessa seuraavasti: ${\displaystyle \mathbb {R} ^{n-1))$

f(p)=(V_{1},V_{2},\dots ,V_{n})

jossa on yhtä suuri kuin positiivisen puolen tilavuus . Tämä funktio f on jatkuva . Borsuk–Ulam-lauseen mukaan pallolla S on antipodaalipisteitä p ja q siten, että . Antipodaalipisteet p ja q vastaavat hypertasoja ja , jotka ovat yhtä suuret lukuun ottamatta positiivisen puolen suuntausta. Silloin se tarkoittaa, että tilavuus on sama positiivisella ja negatiivisella puolella (tai ), kun i =1, 2, …, n −1 . Siten (tai ) on voileivän vaadittu leikkaus, jakamalla tilavuudet puoliksi . $V_{k}$ $A_k$ ${\näyttötyyli \pi (p)}$ $f(p)=f(q)$ ${\näyttötyyli \pi (p)}$ ${\näyttötyyli \pi (q)}$ $f(p)=f(q)$ $A_{i}$ ${\näyttötyyli \pi (p)}$ ${\näyttötyyli \pi (q)}$ ${\näyttötyyli \pi (p)}$ ${\näyttötyyli \pi (q)}$ ${\displaystyle A_{1},A_{2},\dots ,A_{n))$

Versiot mittateoriassa

Mittateoriassa Stone ja Tukey [3] osoittivat kaksi yleisempää sandwich-lauseen muotoa. Molemmat versiot käsittelevät yhteisen joukon X n osajoukon puolittamista , missä X :llä on ulompi Carathéodoryn mitta ja jokaisella osajoukolla on äärellinen ulkomitta. ${\displaystyle X_{,}X_{2},\dots ,X_{n))$ $X_{i}$

Heidän ensimmäinen yleistetty muotoilunsa on seuraava: mille tahansa oikein rajatulle reaalifunktiolle on olemassa piste p n -pallo siten, että pinta, joka jakaa joukon X joukolla ja jakaa samanaikaisesti ulomman suuren . Todistus suoritetaan jälleen pelkistämällä Borsuk-Ulam-lauseeseen. Tämä lause yleistää standardin sandwich-lauseen olettamalla . $f\colon S^{n}\times X\to \mathbb {R}$ $S^{n}$ $f(s,x)=0$ $f(s,x)<0$ $f(s,x)>0$ ${\displaystyle X_{1},X_{2},\dots ,X_{n))$ ${\displaystyle f(s,x)=s_{0}+s_{1}x_{1}+\dots +s_{n}x_{n))$

Heidän toinen yleistetty muotoilunsa on seuraava: kaikille n + 1 mitattavissa oleville X :n funktioille, jotka ovat lineaarisesti riippumattomia mistä tahansa positiivisen suuren X :n osajoukosta , on olemassa lineaarinen yhdistelmä , jossa sekvenssi, joka jakaa X : llä f ( x ) < 0 ja f ( x ) > 0 , puolittaa samanaikaisesti ulkomitat . Tämä lause yleistää standardin sandwich-lauseen, jossa , ja jos i > 0 on vektorin x i :s koordinaatti . ${\displaystyle f_{0},f_{1},\dots ,f_{n))$ ${\displaystyle f=a_{0}f_{0}+a_{1}f_{1}+\dots +a_{n}f_{n))$ $f(x) = 0$ ${\displaystyle X_{1},X_{2},\dots ,X_{n))$ $f_{0}(x)=1$ $korjata)$

Diskreetin ja laskennallisen geometrian versiot

Kombinatorisessa ja laskennallisessa geometriassa sandwich-lause viittaa yleensä erikoistapaukseen, jossa jokainen jaettava joukko on äärellinen pisteiden joukko . Tässä tarkoituksenmukaisin mitta on laskentamitta , joka laskee pisteiden määrän hypertason toisella puolella. Dimensiossa kaksi lause voidaan muotoilla seuraavasti:

Tason äärelliselle pistejoukolle, joka on maalattu "punaisella" ja "sinisellä" väreillä, on viiva , joka jakaa samanaikaisesti punaiset pisteet ja siniset pisteet, eli punaisten pisteiden lukumäärä viivan kummallakin puolella on sama ja sama pätee sinisille pisteille.

On poikkeus, kun pisteet sijaitsevat suoralla. Tässä tapauksessa katsomme jokaisen näistä pisteistä olevan toisella tai toisella puolella tai ei millään puolella viivaa ollenkaan (tämä voi riippua pisteestä), eli "puolittaminen" tarkoittaa itse asiassa, että kumpikin puoli sisältää alle puolet kokonaispistemäärästä. Tämä poikkeustapaus tarvitaan lauseen pätevyyteen, tietysti, kun punaisten pisteiden määrä tai sinisten pisteiden määrä on pariton, mutta myös tietyissä kokoonpanoissa, joissa on parillinen määrä pisteitä, esimerkiksi kun kaikki pisteet ovat päällä sama viiva ja kaksi väriä ovat erotettu toisistaan (ei välissä suoraan). Tilanne, jossa kummankin puolen pisteiden määrä ei täsmää, käsitellään lisäämällä pisteitä viivan ulkopuolelle.

Laskennallisessa geometriassa tämä sandwich-lause johtaa laskennalliseen kinkkuvoileipäongelmaan . Kaksiulotteisessa versiossa ongelma on seuraava: jos tasossa on rajallinen joukko n pistettä, jotka on maalattu "punaisella" ja "sinisellä" väreillä, etsi niille leikkaus kinkkuvoileipästä. Megiddo [4] kuvasi ensin algoritmin erityiselle, erilliselle tapaukselle. Tässä kaikki punaiset pisteet sijaitsevat jonkin viivan toisella puolella ja kaikki siniset pisteet ovat saman viivan toisella puolella. Tässä tilanteessa on olemassa ainoa kinkkuvoileipäleipä, jonka Megiddo voisi löytää lineaarisessa ajassa. Myöhemmin Edelsbrunner ja Wapotich [5] antoivat algoritmin yleiselle kaksiulotteiselle tapaukselle. Heidän algoritminsa ajoaika on , jossa symboli O tarkoittaa O-big . Lopuksi Lo ja Steiger [6] löysivät optimaalisen algoritmin ajoajalla O ( n ) . Lo, Matushek ja Steiger [7] laajensivat tämän algoritmin suuriin ulottuvuuksiin ja algoritmin ajoaika on . Kun annetaan d pistettä yhteisessä paikassa d -ulotteisessa avaruudessa, algoritmi laskee ( d − 1) -ulotteisen hypertason, jolla on yhtä monta pisteitä jokaisessa puoliavaruudessa, eli se antaa kinkkuvoileipäleikkauksen annettuja pisteitä. Jos d sisältyy syötteeseen, ei polynomiaikaalgoritmia odoteta, koska tapauksessa, jossa pisteet ovat momenttikäyrällä , ongelma vastaa kaulakorun leikkaamista , joka on PPA-kova . $O(n\log n)$ $o(n^{d-1})$

Lineaarisen aikaalgoritmin, joka jakaa kaksi ei-leikkautuvaa kuperaa polygonia, kuvasi Stoimenovic [8] .

Yleistykset

Alkuperäinen lause pätee korkeintaan n joukolle , jossa n on dimensioiden lukumäärä. Jos haluamme osioida useampia kokoelmia menemättä suurempiin ulottuvuuksiin, voimme käyttää k -asteen algebrallista pintaa hypertason sijasta , eli ( n − 1 )-ulotteista pintaa, jonka määrittää k -asteen polynomifunktio :

Annetuilla mittasuhteilla n- ulotteisessa avaruudessa on k -asteinen algebrallinen pinta, joka jakaa ne kaikki [9] . ${\binom {k+n}{n}}-1$

Tämä yleistys todistetaan kuvaamalla n -ulotteinen taso -ulotteiseksi tasolle ja soveltamalla sitten alkuperäistä lausetta. Esimerkiksi kun n =2 ja k =2 , 2-ulotteinen taso kartoitetaan 5-ulotteiseen tasoon: ${\binom {k+n}{n}}-1$

{\näyttötyyli (x,y)\to (x,y,x^{2},y^{2},xy)}

Katso myös

Tarkka jako

Kirjallisuus

Beyer WA, Andrew Zardecki. Kinkkuvoileipälauseen varhainen historia // American Mathematical Monthly . - 2004. - T. 111 , numero. 1 . — s. 58–61 . - doi : 10.2307/4145019 . — .
Herbert Edelsbrunner, Waupotitsch R. Kaksiulotteisen kinkkuvoileivän laskeminen // Journal of Symbolic Computation. - 1986. - Osa 2 , numero. 2 . - S. 171-178 . - doi : 10.1016/S0747-7171(86)80020-7 .
Chi-Yuan Lo, Steiger WL Optimaalinen aika-algoritmi kinkku-sandwich-leikkauksille tasossa // Proceedings of the Second Canadian Conference on Computational Geometry. - 1990. - S. 5-9.
Chi-Yuan Lo, Jiri Matousek, William L. Steiger. Algoritmit kinkku-sandwich-leikkauksille // Diskreetti ja laskennallinen geometria . - 1994. - T. 11 , no. 4 . — S. 433–452 . - doi : 10.1007/BF02574017 .
Nimrod Megiddo. Osiointi kahdella rivillä tasossa // Journal of Algorithms. - 1985. - T. 6 , no. 3 . — S. 430–433 . - doi : 10.1016/0196-6774(85)90011-2 .
Smith WD, Wormald NC Geometrisen erottimen lauseet ja sovellukset // Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280). - 1998. - S. 232. - ISBN 0-8186-9172-7 . - doi : 10.1109/sfcs.1998.743449 .
Hugo Steinhaus . Huomautus kinkkuvoileipälauseeseen // Mathesis Polska. - 1938. - T. 9 . — S. 26–28 .
Arthur Harold Stone, John W. Tukey. Yleistetyt "sandwich"-lauseet // Duke Mathematical Journal . - 1942. - T. 9 , no. 2 . — S. 356–359 . - doi : 10.1215/S0012-7094-42-00925-6 .
Ivan Stojmenovic. Kuperien monikulmioiden ja monikulmioiden puolittaminen ja kinkku-sandwich-leikkaukset. // Tietoja. Processing Letts .. - 1991. - T. 38 . — S. 15–21 . - doi : 10.1016/0020-0190(91)90209-Z .

• Hugo Steinhaus "Matemaattinen kaleidoskooppi" -kirjasto • Kvant • numero 8 kääntänyt puolasta F.L. Varpakhovsky Moskova "Science" Fysikaalisen ja matemaattisen kirjallisuuden pääpainos 1981

Linkit

Weisstein, Eric W. Ham Sandwich Theorem (englanniksi) Wolfram MathWorld -verkkosivustolla .
kinkkuvoileipäteoreema joidenkin matematiikan sanojen varhaisimmista tunnetuista käyttötavoista
Danielle MacNevinin kinkkuvoileipäleipat
Interaktiivinen 2D-esittely