Sendvičový teorém

Sendvičová věta říká, že daným n měřitelnými "objekty" v n - rozměrném euklidovském prostoru je lze rozpůlit (podle jejich míry , tj. objemu) jedinou ( n − 1) -rozměrnou nadrovinou .

Tvrzení bylo vysloveno Hugo Steinhausem a dokázáno Stefanem Banachem (v dimenzi tři, bez předpokladu automatického rozšíření věty na n-rozměrný případ) a o rok později bylo toto tvrzení nazváno Stone-Tukeyho věta podle Arthura G. Stone a John Tukey .

Název

Sendvičová věta dostala svůj název podle případu, kdy n = 3 a tři objekty libovolného tvaru jsou plátek šunky a dva plátky chleba . Relativně řečeno sendvič , který lze současně dělit jedním řezem (tedy rovinou ). V dimenzi dvě je věta známá jako věta o palačince , protože spočívá v rozříznutí nekonečně tenké placky na dvě poloviny jediným řezem (tj. přímkou ).

Historie

Podle Bayera a Szardeckého [1] je nejstarším článkem o sendvičové větě, konkrétně pro případ n = 3 řezů tří těles rovinou, článek Steinhause [2] . Článek Bayera a Szardeckého obsahuje překlad článku z roku 1938. Článek připisuje vyjádření problému Hugo Steinhausovi a tvrdí, že Stefan Banach byl první, kdo problém vyřešil redukcí na Borsuk-Ulamovu větu . Článek prezentuje problém dvěma způsoby. První je formální: „Je vždy možné rozdělit tři libovolně umístěná tělesa jednou rovinou?“. Druhý, neformální: "Můžeme pod nůž umístit kousek šunky tak, aby se maso, kost a tuk nožem rozdělily napůl?" Článek nabídl důkaz teorému.

Novějším dokumentem je článek Stonea a Tukeyho [3] , který dal jméno „Stone-Tukey teorém“. Tento článek dokazuje n - rozměrnou verzi věty za obecnějších podmínek měření. Článek přisuzuje případ n = 3 Stanisławu Ulamovi na základě jejich vlastních informací, ale Bayer a Zzardecki [1] tvrdí, že je to nepravdivé, s poukazem na Steinhausův článek, ačkoliv uvádějí: „Ulam zásadním způsobem přispěl k důkazu ' Borsuk-Ulamova věta '."

Dvourozměrná verze: důkaz pomocí "pohyblivého nože"

Dvourozměrnou verzi teorému (také známou jako teorém o palačince ) lze dokázat pomocí argumentů, které se objevují v literatuře o problému krájení dortu (viz například Robertson-Webb's Moving Knife Procedure ).

Pro libovolný úhel můžeme palačinku č. 1 řezat přímkou pod úhlem (abychom to viděli, posuneme přímku pod úhlem od do . Zlomek palačinky č. 1 odříznutý přímkou se plynule mění od 0 do 1, takže podle hodnoty střední věty musí někde nabývat hodnotu 1/2). $\alpha \in [0,180^{\circ }]$ $\alpha$ $\alpha$ $-\infty$ $\infty$

To znamená, že můžeme vzít rovný nůž a otočit s ním o úhel , posouvat jej rovnoběžně na požadovanou vzdálenost, takže palačinka #1 se vždy rozřízne na polovinu v libovolném úhlu. $\alpha \in [0,180^{\circ }]$

Když je nůž pod úhlem 0, krájí i palačinku č. 2, ale její části si nemusí být rovny (pokud jsme měli štěstí a kousky byly stejné, odvedli jsme svou práci). Definujme to jako „kladnou“ stranu nože, u které je podíl palačinky č. 2 větší. Definujeme to jako podíl palačinky č. 2 na kladné straně nože. Zpočátku . $p(\alpha )$ $p(0)\geqslant 1/2$

Když se nůž otočí o 180, bude na stejném místě, ale obráceně, takže . Podle věty o střední hodnotě musí existovat úhel, pod kterým . Řezání s tímto úhlem čepele rozřízne obě palačinky současně na polovinu. $p(180)\leqslant 1/2$ $p(\alpha )=1/2$

n -rozměrná verze: důkaz pomocí Borsuk-Ulamovy věty

Sendvičovou větu lze dokázat následovně pomocí Borsuk-Ulamovy věty . Uvedený důkaz vyplývá z důkazu, který uvedl Steinhaus et al. v článku z roku 1938, připisovaný tam Stefanu Banachovi pro případ n =3 . V oblasti ekvivariantní topologie tento důkaz odpovídá paradigmatu konfigurační prostor/testovací prostor-mapa.

Označme n objektů, které chceme rozdělit na dva současně. Nechť S je jednotková ( n − 1) koule vnořená do n - rozměrného euklidovského prostoru a se středem v počátku . Pro každý bod p na povrchu koule S můžeme definovat kontinuum orientovaných afinních nadrovin (ne nutně přes střed 0) kolmých ( normála ) k vektoru z počátku v p , s "kladným strana" každé nadroviny definované jako strana, na kterou vektor ukazuje (tj. je to volba orientace ). Podle věty o teorému o střední hodnotě každá rodina takových nadrovin obsahuje alespoň jednu nadrovinu, která půlí ohraničený objekt - s jedním extrémním posunutím nebude objem y na kladné straně, ale s extrémním posunutím v druhém směru , celý objem bude na kladné straně , takže mezi těmito extrémy musí být převod, který má poloviční objem na kladné straně . Pokud existuje více než jedna takových nadrovin, můžeme vybrat jednu jako střed půlícího intervalu . Dostaneme tedy pro každý bod p na kouli S nadrovinu , která je kolmá na vektor od počátku k bodu p a která půlí . ${\displaystyle A_{1},A_{2},\dots ,A_{n))$ $\mathbb {R} ^{n}$ $A_{n}$ $A_{n}$ $A_{n}$ $A_{n}$ $\pi (p)$ $A_{n}$

Nyní definujeme funkci f z ( n − 1) -koule S v ( n − 1) -rozměrném euklidovském prostoru takto: ${\displaystyle \mathbb {R} ^{n-1))$

f(p)=(V_{1},V_{2},\tečky ,V_{n})

kde se rovná objemu na kladné straně . Tato funkce f je spojitá . Podle Borsuk–Ulamovy věty existují na kouli S antipodální body p a q takové, že . Antipodální body p a q odpovídají nadrovinám a , které jsou si rovny kromě orientace kladné strany. Pak to znamená, že objem je stejný na kladné i záporné straně (nebo ), pro i =1, 2, …, n −1 . Tedy (nebo ) je požadované řezání sendviče, rozdělení objemů na polovinu . $V_{k}$ $A_k$ $\pi (p)$ $f(p)=f(q)$ $\pi (p)$ $\pi (q)$ $f(p)=f(q)$ $A_{i}$ $\pi (p)$ $\pi (q)$ $\pi (p)$ $\pi (q)$ ${\displaystyle A_{1},A_{2},\dots ,A_{n))$

Verze v teorii míry

V teorii míry Stone a Tukey [3] dokázali dvě obecnější formy sendvičového teorému. Obě verze jsou o půlení n podmnožiny společné množiny X , kde X má vnější Carathéodoryho míru a každá podmnožina má konečnou vnější míru. ${\displaystyle X_{,}X_{2},\dots ,X_{n))$ $X_{i}$

Jejich první zobecněná formulace je následující: pro jakoukoli správně ohraničenou reálnou funkci existuje bod p n -koule takový, že plocha dělící množinu X a současně půlí vnější míru . Důkaz je opět proveden redukcí na Borsuk-Ulamovu větu. Tato věta zobecňuje standardní sendvičovou větu za předpokladu . $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}+\tečky +s_{n}x_{n))$

Jejich druhá zobecněná formulace je následující: pro libovolných n + 1 měřitelných funkcí na X , které jsou lineárně nezávislé na jakékoli podmnožině X kladné míry, existuje lineární kombinace taková, že posloupnost dělící X f ( x ) < 0 a f ( x ) > 0 , současně půlí vnější míry . Tato věta zobecňuje standardní sendvičovou větu, kde , a pro i > 0 je i -tá souřadnice vektoru x . ${\displaystyle f_{0},f_{1},\dots ,f_{n))$ ${\displaystyle f=a_{0}f_{0}+a_{1}f_{1}+\tečky +a_{n}f_{n))$ $f(x)=0$ ${\displaystyle X_{1},X_{2},\dots ,X_{n))$ $f_{0}(x)=1$ $opravit)$

Verze v diskrétní a výpočetní geometrii

V kombinatorické a výpočetní geometrii se sendvičová věta obvykle vztahuje ke speciálnímu případu, kdy každá ze souborů, které mají být rozděleny, je konečný soubor bodů . Zde je nejvhodnější míra počítání , která počítá počet bodů na jedné straně nadroviny. V dimenzi dvě lze větu formulovat takto:

Pro konečnou množinu bodů v rovině, natřených „červenou“ a „modrou“ barvou, existuje čára , která současně půlí červené body a modré body, to znamená, že počet červených bodů na každé straně čáry je totéž a totéž platí pro modré body .

Existuje výjimka, kdy body leží na přímce. V tomto případě považujeme každý z těchto bodů za ležící na jedné nebo na druhé straně nebo na žádné ze stran úsečky (to může záviset na bodu), to znamená, že „půlení“ ve skutečnosti znamená, že každá strana obsahuje méně než polovinu celkového počtu bodů. Tento výjimečný případ je nutný, aby věta platila, samozřejmě, když je počet červených teček nebo počet modrých teček lichý, ale také v určitých konfiguracích se sudým počtem teček, například když všechny tečky leží na stejná čára a dvě barvy jsou od sebe odděleny (ne proložené podél rovně). Situace, kdy se počet bodů na každé straně neshoduje, se řeší přidáním dalších bodů mimo čáru.

Ve výpočetní geometrii vede tento sendvičový teorém k výpočetnímu šunkovému sendvičovému problému . Ve dvourozměrné verzi je problém následující: dáme-li konečnou množinu n bodů v rovině, natřených „červenou“ a „modrou“ barvou, najdeme pro ně řez šunkového sendviče. Megiddo [4] poprvé popsal algoritmus pro speciální, oddělený případ. Zde všechny červené body leží na jedné straně nějaké čáry a všechny modré body leží na druhé straně téže čáry. V této situaci existuje jediný kus šunkového sendviče, který Megiddo dokázal najít v lineárním čase. Později Edelsbrunner a Wapotich [5] poskytli algoritmus pro obecný dvourozměrný případ. Doba běhu jejich algoritmu je , kde symbol O znamená O-big . Nakonec Lo a Steiger [6] našli optimální algoritmus s dobou běhu O ( n ) . Tento algoritmus byl rozšířen do velkých dimenzí Lo, Matushek a Steiger [7] a doba běhu algoritmu je . Je-li dáno d bodů ve společné pozici v d - rozměrném prostoru, algoritmus vypočítá ( d − 1) -rozměrnou nadrovinu, která má stejný počet bodů v každém z poloprostorů, tj. dává šunkový sendvičový řez pro dané body. Pokud je ve vstupu zahrnuto d , pak se neočekává žádný polynomiální časový algoritmus, protože v případě, kdy body leží na momentové křivce , se problém rovná řezání náhrdelníku , což je PPA-tvrdé . $O(n\log n)$ $o(n^{d-1})$

Algoritmus lineárního času, který rozděluje dva neprotínající se konvexní polygony, popsal Stoimenovic [8] .

Zobecnění

Původní věta funguje maximálně pro n kolekcí, kde n je počet dimenzí. Pokud chceme rozdělit více kolekcí, aniž bychom šli do vyšších dimenzí, můžeme místo nadroviny použít algebraickou plochu stupně k , tedy ( n − 1 )-rozměrnou plochu definovanou polynomickou funkcí stupně k :

Dané míry v n - rozměrném prostoru, tam je algebraická plocha stupně k , která půlí je všechny [9] . ${\binom {k+n}{n}}-1$

Toto zobecnění je dokázáno mapováním n - rozměrné roviny do -rozměrné roviny a následným použitím původní věty. Například pro n =2 ak = 2 se 2rozměrná rovina mapuje na 5rozměrnou rovinu: ${\binom {k+n}{n}}-1$

(x,y)\to (x,y,x^{2},y^{2},xy)

Viz také

Přesné rozdělení

Literatura

Beyer WA, Andrew Zardecki. Raná historie teorému o šunkovém sendviči // American Mathematical Monthly . - 2004. - T. 111 , vydání. 1 . — s. 58–61 . - doi : 10.2307/4145019 . — .
Herbert Edelsbrunner, Waupotitsch R. Computing a šunkový sendvič řezaný ve dvou rozměrech // Journal of Symbolic Computation. - 1986. - Vol. 2 , vydání. 2 . — S. 171–178 . - doi : 10.1016/S0747-7171(86)80020-7 .
Chi-Yuan Lo, Steiger WL Optimální časový algoritmus pro šunkové sendvičové řezy v rovině // Proceedings of the Second Canadian Conference on Computational Geometry. - 1990. - S. 5–9.
Chi-Yuan Lo, Jiří Matoušek, William L. Steiger. Algoritmy pro Ham-Sandwich Cuts // Diskrétní a výpočetní geometrie . - 1994. - T. 11 , no. 4 . — S. 433–452 . - doi : 10.1007/BF02574017 .
Nimrod Megiddo. Rozdělení pomocí dvou řádků v rovině // Journal of Algorithms. - 1985. - T. 6 , no. 3 . — S. 430–433 . - doi : 10.1016/0196-6774(85)90011-2 .
Smith WD, Wormald NC Geometrické separátorové teorémy a aplikace // Proceedings 39th Annual Symposium on Foundations of Computer Science (kat. č. 98CB36280). - 1998. - S. 232. - ISBN 0-8186-9172-7 . - doi : 10.1109/sfcs.1998.743449 .
Hugo Steinhaus . Poznámka k větě o šunkovém sendviči // Mathesis Polska. - 1938. - T. 9 . — S. 26–28 .
Arthur Harold Stone, John W. Tukey. Zobecněné „sendvičové“ teorémy // Duke Mathematical Journal . - 1942. - T. 9 , čís. 2 . — S. 356–359 . - doi : 10.1215/S0012-7094-42-00925-6 .
Ivan Stojmenovič. Půlky a šunkové sendvičové řezy konvexních mnohoúhelníků a mnohostěnů. // Informace. Processing Letts .. - 1991. - T. 38 . — S. 15–21 . - doi : 10.1016/0020-0190(91)90209-Z .

• Knihovna Huga Steinhause „Matematický kaleidoskop“ • Kvant • číslo 8 přeloženo z polštiny F.L. Varpakhovským Moskva „Věda“ Hlavní vydání fyzikální a matematické literatury 1981

Odkazy

Weisstein, Eric W. Ham Sandwich Theorem (anglicky) na webových stránkách Wolfram MathWorld .
šunkový sendvičový teorém o nejstarších známých použitích některých slov matematiky
Šunkové sendvičové řezy od Danielle MacNevin
Interaktivní 2D ukázka