Sandwich-sætningen

Sandwich - sætningen siger, at givet n målbare "objekter" i det n - dimensionelle euklidiske rum , kan de halveres (i henhold til deres mål , dvs. volumen) af et enkelt ( n - 1) -dimensionelt hyperplan .

Påstanden blev fremsat af Hugo Steinhaus og bevist af Stefan Banach (i dimension tre, uden at antage en automatisk udvidelse af sætningen til det n-dimensionelle tilfælde), og et år senere blev påstanden kaldt Stone-Tukey-sætningen efter Arthur G. Stone og John Tukey .

Titel

Sandwich-sætningen får sit navn fra tilfældet, når n = 3 og de tre objekter af enhver form er en skive skinke og to skiver brød . Relativt set en sandwich , som kan opdeles samtidigt med et snit (det vil sige med et fly ). I dimension to er sætningen kendt som pandekagesætningen , da den består i at skære en uendelig tynd pandekage i to halvdele med et enkelt snit (dvs. en lige linje ).

Historie

Ifølge Bayer og Szardecki [1] er det tidligste papir om sandwich-sætningen, nemlig for tilfældet med n = 3 snit af tre kroppe ved et fly, papiret af Steinhaus [2] . Bayer og Szardeckis artikel indeholder en oversættelse af artiklen fra 1938. Artiklen tilskriver erklæringen om problemet til Hugo Steinhaus og hævder, at Stefan Banach var den første til at løse problemet ved at reducere til Borsuk-Ulam-sætningen . Artiklen præsenterer problemet på to måder. Den første er formel: "Er det altid muligt at opdele tre vilkårligt placerede kroppe af et plan?". Den anden, uformelle: "Kan vi lægge et stykke skinke under kniven, så kød, ben og fedt bliver delt i to af kniven?" Artiklen gav et bevis på sætningen.

Et nyere papir er afhandlingen af Stone og Tukey [3] , som gav sit navn til "Stone-Tukey-sætningen". Denne artikel beviser den n -dimensionelle version af teoremet under mere generelle måleforhold. Artiklen tilskriver sagen n = 3 til Stanisław Ulam , baseret på deres egne oplysninger, men Bayer og Zzardecki [1] hævder, at dette er falsk, og peger på Steinhaus' papir, selvom de fastslår: "Ulam ydede et grundlæggende bidrag til beviset for ' Borsuk-Ulam-sætningen '."

Todimensionel version: bevis ved hjælp af "bevægelig kniv"

En todimensionel version af sætningen (også kendt som pandekagesætningen ) kan bevises ved hjælp af argumenter, der optræder i litteraturen om det retfærdige kageskæringsproblem (se f.eks. Robertson-Webbs Moving Knife Procedure ).

For enhver vinkel kan vi skære pandekage nr. 1 med en lige linje i en vinkel (for at se dette, vil vi flytte den lige linje i en vinkel fra til . Den del af pandekage nr. 1 afskåret af en lige linje ændres kontinuerligt fra 0 til 1, så ved den mellemliggende sætningsværdi skal den tage værdien 1/2 et sted). $\alpha \in [0,180^{\circ }]$ $\alfa$ $\alfa$ $-\infty$ $\infty$

Det betyder, at vi kan tage en lige kniv og rotere den gennem vinkel , flytte den parallelt med den nødvendige afstand, så pandekage #1 altid skæres i halve for enhver vinkel. $\alpha \in [0,180^{\circ }]$

Når kniven er i en vinkel på 0, skærer den også pandekage #2, men dens dele er måske ikke ens (hvis vi var heldige og stykkerne var lige, gjorde vi vores arbejde). Lad os definere det som den "positive" side af kniven, hvormed andelen af pandekage nr. 2 er større. Vi definerer det som andelen af pandekage nr. 2 på den positive side af kniven. Indledningsvis . $p(\alpha )$ $p(0)\geqslant 1/2$

Når kniven bliver 180, står den samme sted, men på hovedet, så . Ifølge mellemværdisætningen skal der være en vinkel, hvor . Skæring med denne knivvinkel skærer begge pandekager i halve på samme tid. $p(180)\leqslant 1/2$ $p(\alpha )=1/2$

n -dimensional version: bevis ved hjælp af Borsuk-Ulam-sætningen

Sandwich-sætningen kan bevises som følger ved at bruge Borsuk-Ulam-sætningen . Det givne bevis følger det, der blev givet af Steinhaus et al. i papiret fra 1938, tilskrevet der til Stefan Banach , for tilfældet n =3 . Inden for ækvivariant topologi svarer dette bevis til konfigurationsrum/testrum-map-paradigmet.

Lad betegne n objekter, som vi vil dele i to på samme tid. Lad S være en enhed ( n − 1) -kugle indlejret i et n - dimensionelt euklidisk rum og centreret ved origo . For hvert punkt p på overfladen af sfæren S , kan vi definere et kontinuum orienterede affine hyperplaner (ikke nødvendigvis gennem midten 0) vinkelret ( normalen ) på en vektor fra oprindelsen ved p , med "positive side" af hvert hyperplan defineret som den side, som vektoren peger på (det vil sige, det er valget af orientering ). Ved sætningen om mellemværdisætningen indeholder enhver familie af sådanne hyperplaner mindst ét hyperplan, der halverer et afgrænset objekt - med en ekstremal translation vil der ikke være volumen y på den positive side, men med en ekstremal translation i den anden retning , vil hele volumen være på den positive side , så mellem disse yderpunkter skal der være en overførsel, som har halvdelen af volumen på den positive side . Hvis der er mere end et sådant hyperplan, kan vi vælge et som midtpunkt i halverings-bæreintervallet . Således får vi for hvert punkt p på kuglen S et hyperplan , som er vinkelret på vektoren fra origo til punkt p og som halverer . ${\displaystyle A_{1},A_{2},\dots ,A_{n))$ $\mathbb {R} ^{n}$ $A_{n}$ $A_{n}$ $A_{n}$ $A_{n}$ $\pi (p)$ $A_{n}$

Vi definerer nu en funktion f fra ( n − 1) -sfæren S i det ( n − 1) -dimensionelle euklidiske rum som følger: ${\displaystyle \mathbb {R} ^{n-1))$

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

hvor er lig med volumen på den positive side . Denne funktion f er kontinuerlig . Ved Borsuk-Ulam-sætningen eksisterer der antipodale punkter p og q på sfæren S , således at . De antipodale punkter p og q svarer til hyperplanerne og , som er ens bortset fra orienteringen af den positive side. Så betyder det, at volumenet er det samme på den positive og negative side (eller ), for i =1, 2, …, n −1 . Således (eller ) er den påkrævede skæring af sandwichen, der deler mængderne i to . $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))$

Versioner i målteori

I målteorien beviste Stone og Tukey [3] to mere generelle former for sandwich-sætningen. Begge versioner handler om at halvere en n delmængde af en fælles mængde X , hvor X har et ydre Carathéodory- mål , og hver delmængde har et endeligt ydre mål. ${\displaystyle X_{,}X_{2},\dots ,X_{n))$ $X_{i}$

Deres første generaliserede formulering er som følger: For enhver korrekt afgrænset reel funktion eksisterer der et punkt p n -sfære , således at overfladen, der deler mængden X med og samtidig halverer det ydre mål . Beviset udføres igen ved reduktion til Borsuk-Ulam-sætningen. Denne teorem generaliserer standard sandwich-sætningen ved at antage . $f\colon S^{n}\ gange 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))$

Deres anden generaliserede formulering er som følger: for alle n + 1 målbare funktioner på X , der er lineært uafhængige af enhver delmængde af X af positiv måling, eksisterer der en lineær kombination , således at en sekvens, der dividerer X med f ( x ) < 0 og f ( x ) > 0 , halverer samtidigt de ydre mål . Denne sætning generaliserer standard sandwich-sætningen, hvor , og for i > 0 er den i -te koordinat af vektoren x . ${\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$ $rette op)$

Versioner i diskret og beregningsmæssig geometri

I kombinatorisk og beregningsmæssig geometri refererer sandwichsætningen normalt til det særlige tilfælde, hvor hvert af de mængder, der skal opdeles, er et endeligt sæt punkter . Her er det mest passende mål tællemålet , som tæller antallet af punkter på den ene side af hyperplanet. I dimension to kan sætningen formuleres som følger:

For et endeligt sæt af punkter på planet, malet i "røde" og "blå" farver, er der en linje , der samtidigt halverer de røde punkter og blå punkter, det vil sige, at antallet af røde punkter på hver side af linjen er det samme og det samme gælder for blå punkter.

Der er en undtagelse, når punkter ligger på en linje. I dette tilfælde betragter vi hvert af disse punkter for at ligge på den ene eller den anden side, eller på ingen af siderne af linjen overhovedet (dette kan afhænge af punktet), dvs. "halvering" betyder faktisk, at hver side indeholder mindre end halvdelen af det samlede antal point. Dette ekstraordinære tilfælde kræves selvfølgelig for at sætningen holder, når antallet af røde prikker eller antallet af blå prikker er ulige, men også i visse konfigurationer med et lige antal prikker, for eksempel når alle prikkerne ligger på den samme linje og de to farver er adskilt fra hinanden (ikke indsat langs lige). Situationen, hvor antallet af point på hver side ikke stemmer overens, håndteres ved at tilføje yderligere point uden for linjen.

I beregningsgeometri fører denne sandwichsætning til beregningsproblemet med skinkesandwich . I den todimensionelle version er problemet som følger: givet et begrænset sæt af n punkter i planet, malet i "røde" og "blå" farver, find et snit af en skinkesandwich til dem. Megiddo [4] beskrev først algoritmen for et særligt, adskilt tilfælde. Her ligger alle røde punkter på den ene side af en linje, og alle blå punkter ligger på den anden side af den samme linje. I denne situation er der den eneste udskæring af en skinkesandwich, som Megiddo kunne finde i lineær tid. Senere gav Edelsbrunner og Wapotich [5] en algoritme for det generelle todimensionelle tilfælde. Løbetiden for deres algoritme er , hvor symbolet O betyder O-stor . Endelig fandt Lo og Steiger [6] en optimal algoritme med køretid O ( n ) . Denne algoritme blev udvidet til høje dimensioner af Lo, Matushek og Steiger [7] , og algoritmens køretid er . Givet d punkter i en fælles position i et d -dimensionelt rum, beregner algoritmen et ( d − 1) -dimensionelt hyperplan, der har lige mange punkter i hvert af halvrummene, dvs. det giver et skinkesandwichsnit for givet point. Hvis d er inkluderet i inputtet, så forventes der ingen polynomiel tidsalgoritme, da i det tilfælde hvor punkterne ligger på momentkurven , bliver problemet ækvivalent med at skære halskæden , som er PPA-hård . $O(n\log n)$ $o(n^{d-1})$

En lineær tidsalgoritme, der deler to ikke-skærende konvekse polygoner, blev beskrevet af Stoimenovic [8] .

Generaliseringer

Den oprindelige sætning virker højst for n samlinger, hvor n er antallet af dimensioner. Hvis vi ønsker at opdele flere samlinger uden at gå ind i højere dimensioner, kan vi bruge en algebraisk overflade af grad k i stedet for en hyperplan , det vil sige en ( n − 1 )-dimensionel overflade defineret af en polynomisk funktion af grad k :

Givet mål i et n -dimensionelt rum, er der en algebraisk overflade af grad k , der halverer dem alle [9] . ${\binom {k+n}{n}}-1$

Denne generalisering bevises ved at kortlægge et n - dimensionelt plan til et - dimensionelt plan og derefter anvende den oprindelige sætning. For eksempel, for n =2 og k =2 , kortlægges et 2-dimensionelt plan til et 5-dimensionelt plan: ${\binom {k+n}{n}}-1$

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

Se også

Præcis opdeling

Litteratur

Beyer WA, Andrew Zardecki. Den tidlige historie om skinkesandwich-sætningen // American Mathematical Monthly . - 2004. - T. 111 , udg. 1 . — s. 58–61 . - doi : 10.2307/4145019 . — .
Herbert Edelsbrunner, Waupotitsch R. Beregning af en skinkesandwich skåret i to dimensioner // Journal of Symbolic Computation. - 1986. - Vol. 2 , udgave. 2 . — S. 171–178 . - doi : 10.1016/S0747-7171(86)80020-7 .
Chi-Yuan Lo, Steiger WL En optimal tidsalgoritme for skinke-sandwichskæringer i flyet // Proceedings of the Second Canadian Conference on Computational Geometry. - 1990. - S. 5-9.
Chi-Yuan Lo, Jiri Matousek, William L. Steiger. Algoritmer til skinke-sandwichskæringer // Diskret og beregningsgeometri . - 1994. - T. 11 , no. 4 . — S. 433–452 . - doi : 10.1007/BF02574017 .
Nimrod Megiddo. Opdeling med to linjer i planet // Journal of Algorithms. - 1985. - T. 6 , no. 3 . — S. 430–433 . - doi : 10.1016/0196-6774(85)90011-2 .
Smith WD, Wormald NC Geometriske separatorsætninger og anvendelser // 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 . En note om skinkesandwich-sætningen // Mathesis Polska. - 1938. - T. 9 . — S. 26–28 .
Arthur Harold Stone, John W. Tukey. Generaliserede "sandwich"-sætninger // Duke Mathematical Journal . - 1942. - T. 9 , Nr. 2 . — S. 356–359 . - doi : 10.1215/S0012-7094-42-00925-6 .
Ivan Stojmenovic. Halveringer og skinke-sandwich udskæringer af konvekse polygoner og polyedre. // Info. Processing Letts .. - 1991. - T. 38 . — S. 15–21 . - doi : 10.1016/0020-0190(91)90209-Z .

• Hugo Steinhaus "Mathematical Kaleidoscope" Library • Kvant • nummer 8 oversat fra polsk af F.L. Varpakhovsky Moskva "Science" Hovedudgave af fysisk og matematisk litteratur 1981