Ugrás a tartalomhoz

Új matematikai mozaik

Ambrus Gergely, Bárszi Gergely, Csikós Balázs, Frenkel Péter, Gács András, Gyárfás András, Hraskó András, Kiss Emil, Laczkovich Miklós, Lovász László, Montágh Balázs, Moussong Gábor, Pach János, Pelikán József, Recski András, Reiman István

Typotex

A Happy End probléma – A kombinatorikus geometria kezdetei

A Happy End probléma – A kombinatorikus geometria kezdetei

Pach, János


1. Városligeti kör és sokszögek

A történet 1932 őszére nyúlik vissza. Pesti egyetemisták egy kis köre – köztük Erdős Pál, Grünwald (később Gallai) Tibor, Klein Eszter, Szekeres György és Turán Pál – ekkoriban, főként hétvégeken rendszeresen összegyűlt a Városligetben. Az Anonymus-szobornál találkoztak, irodalomról, zenéről, politikáról beszélgettek, múltról és jövőről, álmaikról és csalódásaikról. És még valamiről, ami szenvedélyesen foglalkoztatta őket: a matematikáról. Tulajdonképp már ismeretségüket is a matematikának köszönhették. Gimnazistaként mindannyian a Középiskolai Matematikai és Fizikai Lapok lelkes feladatmegoldói voltak. Fényképen már korábban látták egymást a legeredményesebb diákok arcképcsarnokában, melyet a lap évenként megjelentetett. Az egyetem padjaiban és a Városliget hatalmas platánjai alatt ezek a kapcsolatok aztán életreszóló barátsággá érlelődtek.

Egyik találkozójukra Klein Eszter egy érdekes kis feladattal érkezett. Észrevette, hogy akárhogy veszünk fel öt pontot a síkban úgy, hogy nincs három egy egyenesen, mindig kiválasztható közülük egy konvex négyszög négy csúcsa. A bizonyítás roppant egyszerű. Ha a pontok konvex burkának legalább négy csúcsa van, akkor készen vagyunk. Feltehetjük tehát, hogy a konvex burok egy a b c háromszög, melyen belül még két további pont van: d és e . A d e egyenes szükségképpen elkerüli az a b c háromszög egyik oldalát, mondjuk az a b szakaszt. Ekkor az a , b , d , e pontok nyilván egy konvex négyszöget feszítenek (ld. 1. ábra).

1. ábra. Öt pont mindig meghatároz egy konvex négyszöget

A feladat mindnyájuknak tetszett. A résztvevők visszaemlékezései szerint a társaság férfi tagjainak érdeklődését külön fokozta az a körülmény, hogy a kérdés egy hölgytől származott [26]. A problémát azonnal általánosították.

Egy síkbeli P ponthalmazt általános helyzetűnek mondunk, ha nincs három eleme egy egyenesen. P konvex helyzetben van, ha egybeesik egy konvex sokszög csúcshalmazával. Igaz-e, hogy minden m ? 4 természetes számhoz van egy véges f ( m ) szám, ami eleget tesz a következő feltételnek: akárhogyan is veszünk fel legalább f ( m ) általános helyzetű pontot a síkon, mindig kiválasztható közülük m , amely konvex helyzetben van? Amennyiben ilyen szám létezik, jelölje f ( m ) a legkisebbet.

Makai Endre és Turán Pál hamarosan belátták, hogy f ( 5 ) létezik, méghozzá f ( 5 ) = 9 (ld. 2. ábra). Még a tél beállta előtt Szekeres György büszkén újságolhatta barátainak, hogy minden m -re sikerült igazolnia f ( m ) létezését. Erdős Pál – Szekeres eredeti bizonyítását jócskán megjavítva – sokkal kisebb felső korlátot adott f ( m ) -re. Sőt, nemsokára egy jó konstrukciót is találtak, és azzal a roppant elegáns sejtéssel álltak elő, miszerint minden m -re

f ( m ) = 2 m - 2 + 1 .

Ezt a sejtést – dacára annak, hogy rengeteg profi és amatőr matematikus és komputer-szakember próbálkozott vele – mindmáig senkinek sem sikerült bebizonyítania vagy megcáfolnia. Még az m = 6 eset sem tisztázott, bár Peters és Szekeres számítógépes kísérletei némi reménnyel kecsegtetnek.

2. ábra. Nyolc pont, amely nem határoz meg egy konvex ötszöget

Erdős a feladatot Happy End problémának keresztelte el. Néhány évvel később ugyanis Klein Eszter és Szekeres György összeházasodtak, és máig boldogan élnek. A kérdés mindnyájuk életében és matematikai munkásságában kulcsszerepet játszott.