Skinksmörgåssats

I matematisk måttteori , för varje positivt heltal $n anger$ ham sandwich-satsen att givet $n$ mätbara "objekt" i $n$ - dimensionell euklidisk rymd , är det möjligt att dela var och en av dem på mitten (med avseende på deras mått , t.ex. volym) med ett enda $(n - 1)$ -dimensionellt hyperplan . Detta är även möjligt om objekten överlappar varandra.

Det föreslogs av Hugo Steinhaus och bevisades av Stefan Banach (explicit i dimension 3, utan att göra sig besväret att ange satsen i det $n$ -dimensionella fallet), och även år senare kallad Stone–Tukey-satsen efter Arthur H. Stone och John Tukey .

Namngivning

En skinkmacka

Hamsmörgåssatsen har fått sitt namn från fallet när $n =3$ och de tre föremålen som ska delas är ingredienserna i en skinksmörgås . Källorna skiljer sig åt om dessa tre ingredienser är två skivor bröd och en skinka ( Peters 1981 ), bröd och ost och skinka ( Cairns 1963 ), eller bröd och smör och skinka ( Dubins & Spanier 1961 ). I två dimensioner är satsen känd som pannkakssatsen för att hänvisa till den platta naturen hos de två objekten som ska delas av en linje ( Cairns 1963) .

Historia

Enligt Beyer & Zardecki (2004) är den tidigaste kända uppsatsen om skinksmörgåssatsen, närmare bestämt fallet $n = 3$ att dela tre fasta ämnen med ett plan, en anteckning från 1938 i en polsk matematiktidskrift ( Editers 1938 ). Beyer och Zardeckis papper innehåller en översättning av denna anteckning, som tillskriver Hugo Steinhaus att problemet ställs , och krediterar Stefan Banach som den första att lösa problemet, genom en reduktion till Borsuk–Ulam-satsen . Anteckningen ställer problemet på två sätt: för det första, formellt, som "Är det alltid möjligt att dela tre fasta ämnen, godtyckligt lokaliserade, med hjälp av ett lämpligt plan?" och för det andra, informellt, som "Kan vi placera en bit skinka under en köttskärare så att kött, ben och fett skärs i halvor?" Anteckningen ger sedan ett bevis på satsen.

En mer modern referens är Stone & Tukey (1942), som ligger till grund för namnet "Stone–Tukey theorem". Denna uppsats bevisar den $n$ -dimensionella versionen av satsen i en mer generell miljö som involverar mått. Tidningen tillskriver $n = 3$ till Stanislaw Ulam , baserat på information från en domare; men Beyer & Zardecki (2004) hävdar att detta är felaktigt, med tanke på anteckningen som nämns ovan, även om "Ulam gjorde ett grundläggande bidrag genom att föreslå" Borsuk –Ulam-teoremet .

Tvådimensionell variant: bevis med roterande kniv

Den tvådimensionella varianten av satsen (även känd som pannkakssatsen ) kan bevisas med ett argument som förekommer i den rättvisa kakskärningslitteraturen (se t.ex. Robertson–Webb roterande knivprocedur ).

För varje vinkel $\alpha \in [0,180^{\circ }]$ , kan vi dela pannkaka #1 med en rak linje ("kniv") av vinkeln $\alpha$ . För att se detta, översätt [flytta parallellt] en rak vinkellinje $\alpha$ från $-\infty$ till $\infty$ ; bråkdelen av pannkaka #1 som täcks av linjen ändras kontinuerligt från 0 till 1, så enligt mellanvärdessatsen måste den vara lika med 1/2 någonstans längs vägen. Det är möjligt att en hel rad översättningar av vår linje ger en bråkdel av 1/2; i det här fallet gör vi ett kanoniskt val genom att välja mitten av alla sådana översättningar.

När kniven är i vinkel 0 skär den även pannkaka #2, men bitarna är förmodligen ojämna (har vi tur och bitarna är lika är vi klara). Definiera den "positiva" sidan av kniven som den sida där andelen pannkaka #2 är större. Vi vänder nu kniven och översätter den enligt beskrivningen ovan. När vinkeln är $\alpha$ , definiera $p(\alpha )$ som bråkdelen av pannkaka #2 på den positiva sidan av kniven. Initialt $p(0)>1/2$ displaystyle Funktionen $p$ är kontinuerlig, eftersom små förändringar i vinkeln leder till små förändringar i knivens position.

När kniven är i vinkel 180 är kniven upp och ner, så $)<1/2$ . Med mellanvärdessatsen måste det finnas en vinkel där $p(\alpha )=1/2$ . Att skära i den vinkeln halverar båda pannkakorna samtidigt.

n -dimensionell variant: bevis med Borsuk–Ulam-satsen

Ham sandwich-satsen kan bevisas på följande sätt med hjälp av Borsuk–Ulam-satsen . Detta bevis följer det som beskrevs av Steinhaus och andra (1938), tillskrivet där till Stefan Banach , för fallet $n = 3 .$ Inom området ekvivariant topologi skulle detta bevis falla under paradigmet konfiguration-rymd/test-karta.

Låt $A 1, A 2, \dots, A n$ beteckna de $n$ objekt som vi samtidigt vill dela. Låt $S$ vara enheten $(n - 1)$ -sfär inbäddad i $n$ -dimensionell euklidisk rymd $\mathbb {R} ^{n}$ , centrerad vid origo . För varje punkt $p$ på sfärens $S yta$ kan vi definiera ett kontinuum av orienterade affina hyperplan (inte nödvändigtvis centrerade vid 0) vinkelräta mot ( normala ) vektorn från origo till $p$ , med den "positiva sidan" av varje hyperplan definieras som den sida som vektorn pekar på (dvs det är ett val av orientering ). Enligt mellanvärdessatsen innehåller varje familj av sådana hyperplan minst ett hyperplan som delar det avgränsade objektet $A n$ : vid en extremöversättning finns ingen volym av $A n$ på den positiva sidan, och vid den andra extremöversättningen är hela $A n$ s volym är på den positiva sidan, så däremellan måste det finnas en översättning som har hälften av $A n$ s volym på den positiva sidan. Om det finns mer än ett sådant hyperplan i familjen, kan vi välja ett kanoniskt genom att välja mittpunkten för intervallet av översättningar för vilka $A n$ är delad. Sålunda får vi, för varje punkt $p$ på sfären $S$ , ett hyperplan $π (p)$ som är vinkelrät mot vektorn från origo till $p$ och som delar $A n$ .

Nu definierar vi en funktion $f$ från $(n - 1)$ -sfären $S$ till $(n - 1)$ -dimensionell euklidisk rymd $\mathbb {R} ^{n-1}$ enligt följande:

f (p) = (

volym av

A 1

på den positiva sidan av

π (p)

An -1,

volym av

A 2

på den positiva sidan av

π (p)

, …, volym av på den positiva sidan av

π (p )))

.

Denna funktion $f$ är kontinuerlig (vilket, i ett formellt bevis, skulle behöva någon motivering). Enligt Borsuk–Ulam-satsen finns det antipodalpunkter $p$ och $q$ på sfären $S$ så att $f (p) = f (q)$ . Antipodalpunkter $p$ och $q$ motsvarar hyperplanen $π (p)$ och $π (q)$ som är lika förutom att de har motsatta positiva sidor. Således $f (p) = f (q)$ att volymen av $A i$ är densamma på den positiva och negativa sidan av $π (p)$ (eller $π (q)$ ), för $i = 1, 2, \dots, n -1$ . Således $π (p)$ (eller $π (q)$ ) det önskade skinksmörgåssnittet som samtidigt delar volymerna av $A 1, A 2, \dots, An$ .

Mät teoretiska versioner

I måttteorin bevisade Stone & Tukey (1942) ytterligare två allmänna former av skinkamörgåsteoremet . Båda versionerna avser delning av $n$ delmängder $X 1, X 2, \dots, X n$ av en gemensam mängd $X$ , där $X$ har ett Carathéodory yttre mått och varje $X i$ har ändligt yttre mått.

₀ Deras första allmänna formulering är som följer: för varje kontinuerlig reell funktion $f\colon S^{n}\times X\to \mathbb {R}$ finns en punkt $p$ av n - sfären $S n$ och ett reellt tal s så att ytan $f (p, x) = s 0$ delar $X$ i $f$ $s (p, x) < s 0$ och $f (p, x) > med 0$ samma mått och samtidigt halverar yttre mått på $X 1, X 2, \dots, Xn$ . Beviset är återigen en reducering till Borsuk-Ulam-satsen. Denna sats generaliserar standardsatsen för skinksmörgås genom att låta $f (s, x) = s 1 x 1 + \dots + s n x n$ .

Deras andra formulering är följande: för alla $n + 1$ mätbara funktioner $0 f, f 1, \dots, f n$ över $X$ som är linjärt oberoende av någon delmängd av $X$ av positivt mått, finns det en linjär kombination $00 f = a f + a 1 f 1 + \dots + a n f n$ så att ytan $f (x) = 0$ , som delar $X$ i $f (x) < 0$ och $f (x) > 0$ , samtidigt delar det yttre måttet av $X 1, X 2, \dots Xn__$ . Denna sats generaliserar standardsatsen för skinksmörgås genom att låta $0 f (x) = 1$ och låta $f i (x)$ , för $i > 0$ , vara den $i$ :te koordinaten för $x$ .

Diskreta och beräkningsgeometriversioner

En skinksmörgås med åtta röda punkter och sju blå punkter i planet.

I diskret geometri och beräkningsgeometri hänvisar ham sandwich-satsen vanligtvis till det speciella fallet där var och en av de uppsättningar som delas är en ändlig uppsättning punkter . Här är det relevanta måttet räknemåttet , som helt enkelt räknar antalet punkter på vardera sidan av hyperplanet. I två dimensioner kan satsen uttryckas enligt följande:

För en ändlig uppsättning punkter i planet, var och en färgad "röd" eller "blå", finns det en linje som samtidigt delar de röda punkterna och halverar de blå punkterna, det vill säga antalet röda punkter på vardera sidan av linjen är lika och antalet blå punkter på vardera sidan av linjen är lika.

Det finns ett undantagsfall när punkter ligger på linjen. I den här situationen räknar vi var och en av dessa punkter som antingen på ena sidan, på den andra eller på ingendera sidan av linjen (möjligen beroende på punkten), dvs att "halva" betyder faktiskt att varje sida innehåller mindre än hälften av det totala antalet poäng. Detta undantagsfall krävs faktiskt för att satsen ska hålla, naturligtvis när antalet röda punkter eller antalet blå är udda, men också i specifika konfigurationer med jämna antal punkter, till exempel när alla punkter ligger på samma linje och de två färgerna är separerade från varandra (dvs färgerna växlar inte längs linjen). En situation där antalet punkter på varje sida inte kan matcha varandra tillhandahålls genom att lägga till en extra punkt från linjen i den tidigare konfigurationen.

I beräkningsgeometri leder denna hamsmörgåssats till ett beräkningsproblem, hamsmörgåsproblemet . I två dimensioner är problemet detta: med tanke på en ändlig uppsättning av $n$ punkter i planet, var och en färgad "röd" eller "blå", hitta en skinksmörgås skuren för dem. Först beskrev Megiddo (1985) en algoritm för det speciella, separerade fallet. Här finns alla röda punkter på ena sidan av någon linje och alla blå punkter på andra sidan, en situation där det finns en unik skinksmörgåssnitt, som Megiddo kunde hitta i linjär tid. Senare Edelsbrunner & Waupotitsch (1986) en algoritm för det allmänna tvådimensionella fallet; körtiden för deras algoritm är $O (n log n)$ , där symbolen $O$ indikerar användningen av Big O-notation . Slutligen Lo & Steiger (1990) en optimal $O (n)$ -tidsalgoritm . Denna algoritm utökades till högre dimensioner av Lo, Matoušek & Steiger (1994) där körtiden är $o(n^{d-1})$ . Givet $d$ uppsättningar av punkter i allmän position i $d$ -dimensionellt rymden, beräknar algoritmen ett $(d -1)$ -dimensionellt hyperplan som har lika många punkter av var och en av uppsättningarna i båda sina halvrum, dvs. -smörgåssnitt för de givna poängen. Om $d$ är en del av inmatningen förväntas ingen polynomisk tidsalgoritm existera, som om punkterna är på en momentkurva blir problemet likvärdigt med halsbandsdelning , som är PPA-komplett .

En linjär-tidsalgoritm som area-bisektar två disjunkta konvexa polygoner beskrivs av Stojmenovíc (1991) .

Generaliseringar

Den ursprungliga satsen fungerar för högst $n$ samlingar, där $n$ är antalet dimensioner. Om vi vill dela ett större antal samlingar utan att gå till högre dimensioner kan vi istället för ett hyperplan använda en algebraisk yta av grad k , dvs $en$ ( $n -1$ )–dimensionell yta definierad av en polynomfunktion av grad $k$ :

Givet ${\binom {k+n}{n}}-1$ mått i ett $n$ –dimensionellt utrymme, finns det en algebraisk yta av graden $k$ som delar dem alla. ( Smith & Wormald (1998) ).

Denna generalisering bevisas genom att mappa det $n$ –dimensionella planet till ett ${\binom {k+n}{n}}-1$ dimensionsplan, och sedan tillämpa den ursprungliga satsen. Till exempel, för $n = 2$ och $k = 2$ , mappas det 2-dimensionella planet till ett 5-dimensionellt plan via:

(x, y) \to (x, y, x 2, y 2, xy)

.

Se även

Exakt uppdelning

Beyer, WA; Zardecki, Andrew (2004), "The early history of the ham sandwich theorem" , American Mathematical Monthly , 111 (1): 58–61, doi : 10.2307/4145019 , JSTOR 4145019 , ProQuest 203746537 .
Cairns, Stewart S. (våren 1963), "Networks, ham sandwiches, and putty", Pi Mu Epsilon Journal , 3 (8): 389–403, JSTOR 24338222 .
Dubins, LE ; Spanier, EH (januari 1961), "How to cut a cake fairly", American Mathematical Monthly , 68 (1P1): 1–17, doi : 10.1080/00029890.1961.11989615
Edelsbrunner, Herbert ; Waupotitsch, R. (1986), "Computing a skin sandwich cut in two dimensions", Journal of Symbolic Computation , 2 (2): 171–178, doi : 10.1016/S0747-7171(86)80020-7 .
Lo, Chi-Yuan; Steiger, WL (1990), "An optimal time algorithm for ham-sandwich cuts in the plane", Proceedings of the Second Canadian Conference on Computational Geometry , s. 5–9 .
Lo, Chi-Yuan; Matoušek, Jiří ; Steiger, William L. (1994), "Algorithms for Ham-Sandwich Cuts", Discrete & Computational Geometry , 11 (4): 433–452, doi : 10.1007/BF02574017 .
Megiddo, Nimrod (1985), "Partitionering med två linjer i planet", Journal of Algorithms , 6 (3): 430–433, doi : 10.1016/0196-6774(85)90011-2 .
Peters, James V. (sommaren 1981), "The ham sandwich theorem and some related results", The Rocky Mountain Journal of Mathematics , 11 (3): 473–482, doi : 10.1216/RMJ-1981-11-3-473 , JSTOR 44236614 .
Smith, WD; Wormald, NC (1998), "Geometric separator theorems and applications", Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280) , sid. 232, doi : 10.1109/sfcs.1998.743449 , ISBN 0-8186-9172-7 , S2CID 17962961
Redaktörer (1938), "Notatki: Z topologii", Mathesis Polska (på polska), 11 (1–2): 26–28 .
Stone, Arthur H. ; Tukey, John W. (1942), "Generalized "sandwich" theorems", Duke Mathematical Journal , 9 (2): 356–359, doi : 10.1215/S0012-7094-42-00925-6 .
Stojmenovíc, Ivan (1991), "Bisections and ham-sandwich cuts of convex polygons and polyhedra", Information Processing Letters , 38 (1): 15–21, doi : 10.1016/0020-0190(91)90209-Z .

externa länkar

Weisstein, Eric W. , "Ham Sandwich Theorem" , MathWorld
ham sandwich sats om de tidigaste kända användningarna av några av matematikens ord
Ham Sandwich Cuts av Danielle MacNevin
En interaktiv 2D-demonstration