A szendvicstétel kimondja, hogy adott n mérhető "objektum" az n - dimenziós euklideszi térben , azok (mértékük , azaz térfogatuk szerint) felezhetők egyetlen ( n -1) dimenziós hipersíkkal .
Az állítást Hugo Steinhaus tette, és Stefan Banach bizonyította (a harmadik dimenzióban, nem feltételezve a tétel automatikus kiterjesztését az n-dimenziós esetre), majd egy évvel később az állítást Stone-Tukey tételnek nevezték Arthur G. után. Stone és John Tukey .
A szendvicstétel arról az esetről kapta a nevét, amikor n = 3 , és a három tetszőleges alakú tárgy egy szelet sonka és két szelet kenyér . Relatív értelemben szendvics , amely egyszerre osztható egy vágással (vagyis egy síkkal ). A második dimenzióban a tétel palacsintatétel néven ismert , mivel egy végtelenül vékony palacsintát egyetlen vágással (azaz egyenes vonallal ) kétfelé vágunk .
Bayer és Szardecki [1] szerint a szendvicstételről szóló legkorábbi írás Steinhaus [2] munkája, nevezetesen három test n = 3 síkbeli metszésének esetére . Bayer és Szzardecki cikke tartalmazza az 1938-as cikk fordítását. A cikk Hugo Steinhausnak tulajdonítja a probléma megfogalmazását, és azt állítja, hogy Stefan Banach volt az első, aki megoldotta a problémát a Borsuk-Ulam tétel redukciójával . A cikk kétféleképpen mutatja be a problémát. Az első formális: „Mindig lehetséges-e három tetszőlegesen elhelyezkedő testet egy síkkal kettéosztani?”. A második, kötetlen: "Tehetünk egy darab sonkát a kés alá úgy, hogy a húst, csontot és zsírt kettéosztja a kés?" A cikk a tétel bizonyítását kínálta.
Egy újabb tanulmány Stone és Tukey [3] tanulmánya , amely a "Stone-Tukey-tételnek" adta a nevét. Ez a cikk a tétel n -dimenziós változatát bizonyítja általánosabb mérési feltételek mellett. A cikk az n = 3 esetet Stanisław Ulamnak tulajdonítja, saját információik alapján, de Bayer és Zzardecki [1] amellett érvel, hogy ez hamis, Steinhaus dolgozatára utalva, bár kikötik: "Ulam alapvetően hozzájárult a „ Borsuk-Ulam tétel ”.
A tétel kétdimenziós változata (más néven palacsintatétel ) bizonyítható olyan érvekkel, amelyek a tisztességes tortavágás problémájával foglalkozó szakirodalomban megjelennek (lásd például Robertson-Webb Mozgó késeljárását ).
Az 1. számú palacsintát tetszőleges szögben vághatjuk egyenes vonallal szögben (ennek megtekintéséhez az egyenest szögben mozgatjuk től -ig . Az 1. számú palacsintának egyenes vonallal levágott része folyamatosan változik 0-tól 1-ig, tehát a közbülső tételérték alapján valahol az 1/2 értéket kell vennie).
Ez azt jelenti, hogy vehetünk egy egyenes kést, és szögben elforgathatjuk , a kívánt távolsággal párhuzamosan mozgatva, így az 1. palacsinta minden szögben mindig félbe van vágva.
Amikor a kés 0-s szögben van, akkor a 2-es palacsintát is vágja, de előfordulhat, hogy a részei nem egyenlőek (ha szerencsénk volt és a darabok egyenlőek voltak, akkor elvégeztük a dolgunkat). Határozzuk meg a kés "pozitív" oldalaként, amivel nagyobb a 2. számú palacsinta aránya. Ezt a 2. számú palacsinta arányaként határozzuk meg a kés pozitív oldalán. Kezdetben .
Amikor a kés 180-at forog, ugyanott lesz, de fejjel lefelé, tehát . A köztes érték tétele szerint kell lennie egy szögnek, amelynél . Ezzel a pengeszöggel vágva mindkét palacsintát egyszerre kettévágja.
A szendvicstétel a következőképpen bizonyítható a Borsuk-Ulam tétel segítségével . A megadott bizonyítást követi Steinhaus és munkatársai az 1938-as cikkben, amelyet ott Stefan Banach -nak tulajdonítottak az n =3 esetre . Az ekvivariáns topológia területén ez a bizonyítás megfelel a konfigurációs tér/teszt tértérkép paradigmának.
Jelöljön n objektumot, amelyet egyszerre ketté akarunk osztani. Legyen S egy n - dimenziós euklideszi térbe ágyazott egység ( n − 1) -gömb , amelynek középpontja az origóban van . Az S gömb felületén lévő minden p ponthoz meghatározhatunk egy kontinuumot orientált affin hipersíkokból (nem feltétlenül a 0 középponton keresztül), amelyek merőlegesek ( a normálisra ) a p origóból származó vektorra , a "pozitív" oldala" minden hipersík oldalként definiált oldalaként, amelyre a vektor mutat (azaz az orientáció megválasztása ). A közbülső érték tételére vonatkozó tétel szerint az ilyen hipersíkok bármely családja tartalmaz legalább egy hipersíkot, amely kettészel egy korlátos objektumot - egy extremális transzláció esetén nem lesz y térfogat a pozitív oldalon, hanem extremális transzlációval a másik irányba , a teljes hangerő a pozitív oldalon lesz, tehát e szélsőségek között kell lennie egy átvitelnek, amelynek a hangerő fele a pozitív oldalon . Ha egynél több ilyen hipersík van, választhatunk egyet a felező-hordozó intervallum felezőpontjaként . Így az S gömb minden p pontjára egy hipersíkot kapunk , amely merőleges az origótól a p pontig tartó vektorra, és felezi a -t .
Most egy f függvényt definiálunk az ( n - 1) -S gömbből az ( n - 1) -dimenziós euklideszi térben a következőképpen:
ahol egyenlő a pozitív oldal térfogatával . Ez az f függvény folytonos . A Borsuk–Ulam tétel szerint léteznek olyan p és q antipodális pontok az S gömbön , hogy . A p és q antipodális pontok a és hipersíkoknak felelnek meg , amelyek egyenlőek, kivéve a pozitív oldal orientációját. Ekkor ez azt jelenti, hogy a térfogat azonos a pozitív és negatív oldalon (vagy ), i =1, 2, …, n −1 esetén . Így (vagy ) a szendvics szükséges darabolása, a térfogatok felére osztva .
A mértékelméletben Stone és Tukey [3] a szendvicstétel két általánosabb formáját bizonyította. Mindkét változat egy X közös halmaz n részhalmazának felezéséről szól , ahol X - nek van egy külső Carathéodory -mértéke , és mindegyik részhalmaznak van véges külső mértéke.
Első általánosított megfogalmazásuk a következő: minden megfelelően korlátos valós függvényhez létezik egy p n -pontú gömb , amelyben az X halmazt elosztó felület a külső mértékkel egyidejűleg felezi . A bizonyítást ismét a Borsuk-Ulam tételre redukálva hajtjuk végre. Ez a tétel általánosítja a standard szendvicstételt, feltételezve .
Második általánosított megfogalmazásuk a következő: X-en bármely n + 1 mérhető függvényre , amely lineárisan független a pozitív mérték X bármely részhalmazától , létezik olyan lineáris kombináció , amely szerint egy sorozat, amely X - et osztja f -vel ( x ) < 0 és f ( x ) > 0 , egyidejűleg felosztja a külső mértékeket . Ez a tétel általánosítja a standard szendvicstételt, ahol , és i > 0 esetén az x vektor i -edik koordinátája .
A kombinatorikus és számítási geometriában a szendvicstétel általában arra a speciális esetre vonatkozik, amikor a felosztandó halmazok véges ponthalmazok . Itt a legmegfelelőbb mérték a számláló mérték , amely a hipersík egyik oldalán lévő pontok számát számolja. A második dimenzióban a tétel a következőképpen fogalmazható meg:
A síkon egy véges ponthalmazhoz, amely "piros" és "kék" színnel van festve, van egy vonal , amely egyidejűleg felosztja a piros és a kék pontokat, azaz a piros pontok száma a vonal mindkét oldalán ugyanez és ugyanez igaz a kék pontokra is .Van kivétel, amikor a pontok egy egyenesen helyezkednek el. Ebben az esetben ezeket a pontokat úgy tekintjük, hogy az egyik vagy a másik oldalon, vagy egyáltalán egyik oldalon sem találhatók (ez a ponttól függhet), vagyis a "felezés" valójában azt jelenti, hogy mindkét oldal kevesebb mint a felét tartalmazza az összes pontnak. Ez a kivételes eset természetesen szükséges ahhoz, hogy a tétel érvényesüljön, ha a piros pontok száma vagy a kék pontok száma páratlan, de bizonyos konfigurációkban is páros számú pont esetén, például amikor az összes pont ugyanaz a vonal és a két szín el van választva egymástól (nem egyenes mentén). Azt a helyzetet, amikor az egyes oldalakon lévő pontok száma nem egyezik, a vonalon kívüli további pontok hozzáadásával kezeljük.
A számítási geometriában ez a szendvics-tétel a számítási ham-szendvics problémához vezet . A kétdimenziós változatban a probléma a következő: adott a síkban egy véges n pontból álló halmaz, amely "piros" és "kék" színnel van festve, keressen nekik egy sonkás szendvicset. Megiddo [4] először egy speciális, elkülönített esetre írta le az algoritmust. Itt az összes piros pont valamelyik vonal egyik oldalán, az összes kék pont pedig ugyanazon vonal másik oldalán található. Ebben a helyzetben a sonkás szendvics egyetlen darabja van, amelyet Megiddo lineáris időben találhat. Később Edelsbrunner és Wapotich [5] adott egy algoritmust az általános kétdimenziós esetre. Algoritmusuk futási ideje , ahol az O szimbólum O -nagyot jelent . Végül Lo és Steiger [6] talált egy optimális algoritmust O ( n ) futási idővel . Ezt az algoritmust Lo, Matushek és Steiger [7] kiterjesztette nagy dimenziókra, és az algoritmus futási ideje . Adott d pont egy d -dimenziós térben egy közös pozícióban , az algoritmus kiszámít egy ( d − 1) -dimenziós hipersíkot, amelynek minden félterében egyenlő számú pont van, azaz egy sonkás szendvicset ad a adott pontokat. Ha d szerepel a bemenetben, akkor nem várható polinomiális idő algoritmus, mivel abban az esetben, ha a pontok a nyomatékgörbén helyezkednek el , a probléma egyenértékűvé válik a nyaklánc vágásával , ami PPA-kemény .
Stoimenovic [8] írt le egy lineáris időalgoritmust, amely két nem metsző konvex sokszöget oszt fel .
Az eredeti tétel legfeljebb n gyűjteményre működik, ahol n a dimenziók száma. Ha több gyűjteményt szeretnénk particionálni anélkül, hogy nagyobb dimenziókba mennénk, akkor hipersík helyett használhatunk k fokú algebrai felületet, azaz egy k fokú polinomfüggvénnyel meghatározott ( n − 1 )-dimenziós felületet :
Adott mértékek egy n -dimenziós térben, van egy k fokú algebrai felület, amely mindegyiket kettéosztja [9] .
Ezt az általánosítást úgy bizonyítjuk, hogy egy n - dimenziós síkot leképezünk egy -dimenziós síkra, majd alkalmazzuk az eredeti tételt. Például n =2 és k =2 esetén egy 2-dimenziós sík egy 5-dimenziós síkra van leképezve:
.• Hugo Steinhaus „Matematikai Kaleidoszkóp” Könyvtár • Kvant • 8. szám lengyelről fordította F.L. Varpakhovsky Moszkva „Tudomány” Fizikai és matematikai irodalom főkiadása 1981