Sonkásszendvicstétel

A sonkásszendvicstétel a mértékelmélet és a topológia egy tétele. Azt állítja, hogy ha adva van az n dimenziós térben n páronként diszjunkt test úgy, hogy mindegyik minden irányban elfelezhető, akkor van egy hipersík, ami mindegyiket elfelezi. Az elfelezés érthető úgy is, hogy az n dimenziós térfogatot felezi. Véges ponthalmazokra alkalmazva az elemszám a mérték. Nevezik Stone–Tukey-tételnek is.

Története

William Aaron Beyer és Andrew Zardecki cikke (2004) szerint a tétel első változata, speciálisan a háromdimenziós esetre, Hugo Steinhausnál bukkant fel először 1938-ban. Beyer és Zardecki cikke tartalmazza Steinhaus cikkének fordítását. Steinhaus kétféleképpen is leírta, formálisan: Elfelezhető-e mindig két test egy síkkal, akárhol is vannak a térben? és informálisan: Kettévágható-e késsel egy sonka úgy, hogy a vágás a húst, a csontot és a zsírt is elfelezze? A cikk a Borsuk–Ulam-tétel felhasználásával be is bizonyítja a tételt. Az általános esetet Arthur Harold Stone és John Tukey (1942) oldotta meg. Az n=3 speciális esetet S. M. Ulamnak tulajdonították, ám Beyer és Zardecki szerint tévesen.

Bizonyítás

Ez a háromdimenziós eset bizonyítása. Más dimenziókban hasonlóan látható be.

Tekintjük az adott irányú síkok közös normálvektorát, v-t. A normálvektor és a síkok közötti kapcsolat folytonos. Nevezzük ezeket a síkokat σ_A-nak, σ_B-nek és σ_C-nek. Jelölje f₁ a σ_A és a σ_B síkok, és f₂ a σ_A és a σ_C távolságát úgy, hogy v iránya pozitív. Legyen f(v)=(f₁(v),f₂(v)). Ez egy páratlan függvény, mivel előjeles távolságokat mér. A Borsuk–Ulam-tétel szerint viszont van v vektor, amire ugyanazok lesznek a távolságok. Ez csak úgy lehet, ha ezek a távolságok mind nullák, vagyis a síkok egybeesnek.

Mértékelméleti változatai

Stone és Tukey a tétel két általánosabb formáját is bizonyította. Mindkét verzió az n dimenziós tér egy X halmazának elfelezéséről szól, ahol is az X halmaz n diszjunkt részből áll. Az X halmaznak van külső Carathéodory-mértéke, és a diszjunkt X₁, X₂,… X_n halmazok külső X₁-mértéke véges.

Az egyik általánosítás szerint minden $f:S^{n}\times X\to \mathbb {R}$ függvényhez van olyan p pontja az Sⁿ gömbnek, hogy az f(p,x) = 0 felület felezi nemcsak X, hanem X₁, X₂,… X_n külső Carathéodory-mértékét is. Ez szintén belátható a Borsuk–Ulam tétellel.

A másik általánosítás szerint, ha X-en értelmezve vannak az f₀, f₁, …, f_n mérhető függvények, amik lineárisan függetlenek X egy pozitív mértékű részhalmazán, akkor van olyan f=a₀f₀+a₁f₁+ … +a_nf_n lineáris kombinációjuk, hogy az f(x)=0 felület felezi nemcsak X, hanem X₁, X₂,… X_n külső Carathéodory-mértékét is.

A véges és a számítógépi geometriában

A véges és a számítógépi geometriában a sonkásszendvicstételt véges ponthalmazokra vonatkoztatják. Itt a mértéket a halmazok elemszáma adja. Tehát a tétel szövege a síkbeli esetre vonatkoztatva:

Akárhogy is van megadva a síkon véges sok piros és véges sok kék pont, mindig van egyenes, ami úgy osztja két részre a síkot, hogy a piros és a kék pontok halmazát is megfelezi, vagyis az egyenes egyik oldalán levő piros pontok száma megegyezik a másik oldalon levő piros pontok számával, és ugyanígy, az egyenes egyik oldalán fekvő kék pontok száma egyenlő a másik oldalon fekvő kék pontok számával.

Egyes konfigurációk esetén a felező egyenes átmegy néhány piros, vagy kék ponton. Ez történik például, ha valamelyik ponthalmaz páratlan sok pontból áll, de megeshet akkor is, ha a piros és a kék pontok száma egyaránt páros. Ezekben az esetekben mindkét oldalhoz hozzászámítjuk azokat a pontokat, amik illeszkednek az egyenesre, azaz ha szigorúan vesszük, akkor mindkét oldalra a pontoknak legfeljebb a fele került. A tétel ekkor is teljesül.

A számítógépi geometriában megfogalmazott feladat a sonkásszendvics feladat: adva van a síkon néhány piros és kék pont, keressünk hozzájuk egy felező egyenest! Az első algoritmus Megiddotól származik (1985) arra a speciális esetre, amikor a piros és a kék pontok egy egyenessel elválaszthatók. Ekkor Megiddo algoritmusa lineáris időben talált felező vágást. Edelsbrunner és Waupotitsch algoritmusa (1986) az általános esetben is működött O(n log n) futási idővel, ahol is 'O a nagy ordo jelölés. Lo és Steiger algoritmusa (1990) már lineáris időben talált felező vágást. Lo, Matoušek és Steiger ezt az algoritmust (1994) kiterjesztette magasabb dimenziós esetekre is.

Források

• Szűcs András: Topológia
• Beyer, W. A. & Zardecki, Andrew (2004), "The early history of the ham sandwich theorem", American Mathematical Monthly 111 (1): 58–61, doi:10.2307/4145019, <http://proquest.umi.com/pqdweb?did=526216421&Fmt=3&clientId=5482&RQT=309&VName=PQD>.
• Edelsbrunner, H. & Waupotitsch, R. (1986), "Computing a ham sandwich cut in two dimensions", J. Symbolic Comput. 2: 171–178, DOI 10.1016/S0747-7171(86)80020-7.
• Lo, Chi-Yuan & Steiger, W. L. (1990), "An optimal time algorithm for ham-sandwich cuts in the plane", Proceedings of the Second Canadian Conference on Computational Geometry, pp. 5–9.
• Lo, Chi-Yuan; Matoušek, Jiří & Steiger, William L. (1994), "Algorithms for Ham-Sandwich Cuts", Discrete and Computational Geometry 11: 433–452, DOI 10.1007/BF02574017.
• Megiddo, Nimrod (1985), "Partitioning with two lines in the plane", Journal of Algorithms 6: 430–433, DOI 10.1016/0196-6774(85)90011-2.
• Steinhaus, Hugo (1938), "A note on the ham sandwich theorem", Mathesis Polska 9: 26–28.
• Stone, A. H. & Tukey, J. W. (1942), "Generalized "sandwich" theorems", Duke Mathematical Journal 9: 356–359, doi:10.1215/S0012-7094-42-00925-6, <http://projecteuclid.org/euclid.dmj/1077493229>.

További információk

• Weisstein, Eric W.: Ham Sandwich Theorem (angol nyelven). Wolfram MathWorld
• ham sandwich theorem on the Earliest known uses of some of the words of mathematics
• Ham Sandwich Cuts by Danielle MacNevin

Fordítás

Ez a szócikk részben vagy egészben a Ham sandwich theorem című angol Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.