A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre. 1. E kis cikkben egy elemi geometriai kérdéssel kapcsolatos megoldott és megoldatlan problémákról lesz szó. Remélem, sikerülni fog az olvasót meggyőznöm, hogy még az elemi geometria évezredek óta vizsgált területén is sok az új és egyszerű segédeszközökkel bizonyítható eredmény. 1933-ban olvastam Hilbert‐Cohn-Vossen ,,Anschauliche Geometrie'' (szemléletes geometria) című szép könyvét. E könyv geometriai konfigurációkról szóló fejezetének olvasása közben a következő probléma jutott eszembe: Legyen adva a síkban pont, melyek nincsenek mind egy egyenesen, akkor van oly egyenes, mely ezen pont közül pontosan kettőn megy át. Úgy gondoltam, ez magától értetődő lesz, de nem tudtam bebizonyítani. Elmondtam e sejtést Gallai Tibornak, aki hamarosan szép bizonyítást talált e tételre. 1936-ban az oslói nemzetközi matematikai kongresszuson Karamata kérdezett e tételről, mondotta, hogy egy régi mechanika könyvben olvasta s ő sem tudta bebizonyítani. Elmondtam neki Gallai bizonyítását. 1943-ban kitűztem a problémát az American Mathematical Monthly c. folyóirat probléma-rovatában. Több érdekes megoldás érkezett, a legszebb Kellyé, mely még Gallaiénál is szellemesebb, s melyet most közlök.
1. ábra 2. Legyenek az adott pontok . Kössük össze bármely két -t. Így nyerjük az egyeneseket. Minthogy a pontok nincsenek mind egy egyenesen, . Tekintsük mindegyik távolságát mindegyik -től, mely nem megy át -n. Legyen ezen távolságok legkisebbike például távolsága -től (a pontok és egyenesek számozása természetesen tetszőleges). Azt állítom, hogy az egyenesen pontosan két van. Jelentse a -ből -re bocsátott merőleges talppontját (1. ábra). Ha -en három lenne, akkor valamelyik oldalán legalább két ily pont lenne, e pontok legyenek és úgy, hogy és között van (esetleg -vel egybeesik). Ekkor azonban világos, hogy távolsága a egyenestől kisebb mint , a pont távolsága az egyenestől (tudniillik távolsága kisebb vagy egyenlő, mint a derékszögű háromszögnek az átfogóra bocsátott magassága, és nagyobb ennél), s ezzel Gallai tételét be is bizonyítottuk. 3. Kelly a probléma eredetét is megtalálta. 1893-ban Sylvester közölte e problémát az Educational Times c., azóta megszűnt folyóiratban. Megoldás e feladatra akkor nem érkezett, s nincs adat arra, vajon Sylvesternek volt-e megoldása problémájára, s így a tételt Gallai tételének nevezik. Kelly bizonyítását Coxeter közölte. 1949-ben megismerkedtem Motzkinnal. Elmondta, hogy 1933-ban (Sylvesterről s rólunk nem tudva) ő is felvetette e kérdést, s 1939-ben A. Robinson bebizonyította a tételt. 4. Gallai tételével kapcsolatban számos további probléma merül fel. Hogy röviden tudjuk kifejezni magunkat, nevezzünk ‐ ha adva van a síkban pont, melyek nincsenek mind egy egyenesen ‐, közönséges egyenesnek egy olyan egyenest, mely e pontok közül pontosan kettőn megy át. Gallai tétele szerint mindig legalább egy közönséges egyenes van. Ha a pontok általános helyzetben vannak (nincs semelyik 3 egy egyenesen), a közönséges egyenesek száma . Ha pont van egy egyenesen, és az -edik az egyenesen kívül, akkor a közönséges egyenesek száma . Jelentse mármost a közönséges egyenesek minimális számát. De Bruijnnel sejtettük, hogy -nel együtt minden határon túl nő, vagyis akárhogy is adunk meg egy egész számot, létezik egy csak -tól függő szám úgy, hogy bárhogyan is adunk meg a síkban -nál több pontot, amelyek nincsenek mind egy egyenesen, ezek legalább közönséges egyenest határoznak meg.
2. ábra G. Dirac bebizonyította, hogy . E becslés -ra, -re, -ra és -re pontos, amint azt a 2. ábra példái mutatják. Motzkin bebizonyította, hogy , és ezzel sejtésünket igazolta. Legújabb időben Kelly és Moser bebizonyították, hogy ; ez megint pontos -re, nincs azonban kizárva, hogy nagy értékeire a tétel még javítható, például igaz lehetne a következő sejtés: Létezik egy olyan egész szám, hogy ha és tetszőleges pont a síkban, melyek nincsenek mind egy egyenesen, akkor ezek legalább közönséges egyenest határoznak meg. Ez azt jelentené: hogyha , akkor (ti. már említettük, hogy ha pont egy egyenesen van, akkor közönséges egyenest nyerünk, s ezért minden -re . G. Dirac sejtette, hogy esetén . 5. Még 1933-ban észrevettem, hogy Gallai tételéből következik, hogy ha a síkban pont van adva, melyek nincsenek mind egy egyenesen, akkor ezek legalább egyenest határoznak meg, azaz azon egyenesek száma, melyek e pontok közül legalább kettőn átmennek, nem lehet -nél kisebb. A bizonyítás Gallai tételének segítségével könnyű (lásd az 1183. feladatot). Nyilvánvaló, hogy e tétel pontos, ha ugyanis pont van egy egyenesen, s az -edik pont nincs ezen az egyenesen, akkor e pontok nyilván egyenest határoznak meg. Sejtettem, hogy ha az pont olyan, hogy nincs közülük sem egy egyenesen, és elég nagy szám, akkor ezek legalább egyenest határoznak meg. Ez kis -ekre, pl: -ra nem igaz. A 2. c), d) ábrán és a 3. ábrán pont esetén rendre , , ill. egyenest látunk, pedig ezekre az -ekre , , ill. . Kelly és Moser a már idézett cikkükben a következő általános tételt bizonyítják be:
3. ábra Tegyük fel, hogy az pont olyan, hogy legfeljebb van közülük egy egyenesen, tegyük fel továbbá, hogy akkor az pont legalább egyenest határoz meg. Nem feltétlenül határoznak meg a pontok (2)-nél több egyenest, mint ezt a szerzők következő példája mutatja: legyen pont a síkban úgy, hogy nincs közülük három egy egyenesen, a sík egy tetszőleges egyenese, mely a , pontok egyikén sem megy át. A , egyenesek ‐ számuk ‐ az egyenest a pontokban metszik. A többi pontot az egyenesen tetszőlegesen vesszük fel. Könnyű belátni, hogy ez az pont | | egyenest határoz meg. Legyen mármost . ‐ (1) és (2) igazolja sejtésemet, ha . Kelly és Moser kimutatták, hogy sejtésem -re is igaz (azaz pont, melyek közül nincs egy egyenesen, legalább egyenest határoz meg), s sejtik, hogy a értékekre is igaz. Bebizonyították továbbá, hogy ha , , akkor legalább egyenest nyerünk, s láttuk (2. c), d) ábra és 3. ábra), hogy nem is javítható. 6. Kelly és Moser eredményei azonban még nem intézik el teljesen az itt felmerülő problémákat. Nyilvánvaló pl., hogy létezik egy oly szám, hogy ha adva van pont, melyek közül legfeljebb van egy egyenesen, akkor e pontok legalább egyenest határoznak meg, például vehetjük -t -nak. (2)-ből -ra ennél lényegesen jobb becslést kaphatunk, de különböző -ra különbözó értékeket. A kérdés azonban az, hogy van-e oly szám, mely minden -ra jó. Azaz valószínűleg igaz a következő sejtés: Létezik oly állandó, (mely nem függ sem -tól, sem -től), hogy ha az pont közül legfeljebb van egy egyenesen, akkor a fellépő egyenesek száma nagyobb, mint (feltehető, hogy a sejtés igaz, ha ). Említsük meg még Dirac következő sejtését: Legyen pont a síkban, melyek nincsenek mind egy egyenesen, akkor mindig van egy pont úgy, hogy a , , egyenesek közül legalább különböző van. Megemlítjük még, hogy Sylvester a következő kérdést vizsgálta: Legyen adva pont, a síkban. Maximálisan hány olyan egyenes lehetséges, mely e pontok közül pontosan hármon megy át? Kimutatta, hogy -re e maximum . Könnyű belátni, hogy általában -re e maximum nem nagyobb, mint (ennyi volna, ha minden egyenesen pont volna) és Gallai tétele miatt e maximum semmilyen -re nem érheti el az értéket. Páros -re e maximum legfeljebb . (Ez abból látható be, hogy minden ponton kell olyan egyenesnek átmennie ez esetben, amin páros számú pont van.) E tételek részletes bizonyítását az olvasóra bízom. Nagyon meglepő azonban, hogy Sylvester kimutatta, hogy e maximum nagyobb, mint , ahol alkalmas, -től nem függő állandó. Kérdezhetjük még azt is, hogy mekkora azon egyenesek maximális száma; amelyek az pont közül pontosan négyen mennek át. Ezt csak speciális értékeire vizsgálták, és én azt hiszem, hogy nagy -re e maximum sokkal kisebb nagyságrendű lesz, mint , talán kisebb, mint , egy alkalmas állandóval. 7. Most rátérek e kérdések kombinatorikus általánosításaira. Legyenek elemek, az elemekből alkotott, legalább kételemű csoportok (szokásos szakkifejezéssel halmazok). Feltesszük, hogy minden pár egy és csakis egy -ben fordul elő. Ha az -k pontok, és az -k azon egyenesek, melyek e pontok közül legalább kettőn átmennek, akkor nyilván e feltételt kielégítő rendszert kapunk. Azonban könnyű belátni, hogy lehet olyan , , , rendszert csinálni, mely nem valósítható meg, mint a sík pontjai és egyenesei. Legyen ugyanis , és az -k: , , , , , , . E rendszer nyilván nem valósítható meg a síkban, ti. e rendszernek nincsen közönséges egyenese, azaz nincs oly , mely pontosan két -t tartalmaz. Ennek ellenére fennáll a követező tétel: Ha , akkor ‐ azaz ha az -k száma nagyobb, mint egy, akkor legalább van. Ez lényeges általánosítása annak a tételnek, hogy pont a síkban, ha nincs mind egy egyenesen, legalább egyenest határoz meg. E tételt Hanani bizonyította be először 1938-ban. Én Hanani eredményéről nem tudva, 1941-ben újra felfedeztem e tételt, melyet Szekeres is bebizonyított. A legegyszerűbb bizonyítás de Bruijn-től való, melyet most közlök. 8. Két elem és nyilván egyértelműen meghatároz egy halmazt, éspedig azt, amely az párt tartalmazza. Feltevésünk szerint egy és csakis egy ily van. Hogy röviden tudjam magam kifejezni, az elemeket pontoknak fogom nevezni s az halmazokat utaknak. Jelöljük az ponton átmenő utak számát -vel, az úton levő pontok számát -vel. Nyilván , és , minthogy a pontok nincsenek mind egy út mentén, és minden úton legalább két pont van. A -k és -k közt könnyen találhatunk egy összefüggést p1. a következő szemléletes meggondolással: képzeljük az utakat villamosvonalaknak, amelyeknek minden pontban (kereszteződésnél) megállójuk van . Egy alkalommal minden vonalon végighaladt egy villamos, és mindegyikre minden megállónál egy utas szállt fel. Ekkor az kereszteződésnél felszálló volt, az vonalon utas utazott, tehát az összes utasokat egyrészt útvonalak, másrészt állomások szerint összeszámolva a következő azonosságot kapjuk: | | (3) |
Feltehetjük, hogy a pontok a rajtuk átmenő utak csökkenő száma szerint vannak rendezve, tehát | | (4) | továbbá, hogy az -en az utak mennek át. Jelöljük -et, miután sok szó lesz még róla, rövidebben -vel. Keressünk összefüggéseket a -k és -ek közt. Ha az út nem megy át az ponton, akkor -t minden egyes pontjával más-más út köti össze, mert különben volna két olyan út, amelyek két különböző pontban találkoznak, pedig feltettük, hogy ilyen nincs. Így, ha nem megy át -n, akkor Ezt alkalmazhatjuk és -re: Ezeket összeadva | | (6) |
Az -t is tudjuk becsülni -kkal (5) alapján, ugyanis átmegy egy -től különböző ponton ‐ feltehetjük, hogy ezt jelöltük -gyel ‐, mert minden út legalább két ponton halad át. Ekkor nem mehet át -en, mert két út legfeljebb egy pontban találkozik, így (5) szerint fennáll pl. De is átmegy egy -től (és -től) különböző ponton, mondjuk -n. Ezen nem megy át, tehát pl. Hasonlóan haladva tovább, végül az -en találunk egy -től különböző pontot, amelyen nem megy át, -n pedig egy pontot, amin az előző -k, p1. nem megy át. Így (5) alapján a következő egyenlőtlenségeket kapjuk: | |
Ezeket összeadva és hozzájuk adva (6)-ot, azt kapjuk, hogy | |
Írjuk itt be a jobb oldal helyébe (3) jobb oldalát, majd alkalmazzuk -re (4)-et, kapjuk, hogy
Innen és mivel , Ezzel bebizonyítottuk Hanani tételét. 9. Az egyenesekre tárgyalt problémához hasonlóak körökkel kapcsolatban is felmerülnek. Érvényes Gallai tételének következő általánosítása: Legyenek adva a síkban a pontok , amelyek nincsenek mind egy körön, akkor van olyan kör, amelyik pontosan három -n megy át. A tétel (mely említve van a lábjegyzetben idézett cikkben), Gallai tételéből könnyen következik az inverzió, más néven körre vonatkozó tükrözés nevű transzformáció segítségével. Tegyük fel ugyanis, hogy a tétel nem volna igaz. Ekkor volna egy olyan pontrendszer, amelynek bármely három pontján átmenő kör egy negyedik -n is átmenne, így többek közt minden ponthármason átmenő kör átmenne egy negyedik ponton is. Alkalmazzunk ekkor inverziót egy középpontú körre, a pont képét jelöljük -vel . Ebben a pontrendszerben a egyenes a , , pontokon átmenő kör képe, s így feltétel szerint átmegy legalább még egy ponton. Ez azonban Gallai tétele szerint csak úgy lehet, ha mind egy egyenesen van, de ez az egyenes akkor egy -en is átmenő kör képe volna, holott feltétel szerint nincs az összes egy körön. Lehetetlenségre jutottunk, kell tehát, hogy a körökre vonatkozó tétel is igaz legyen. Nem látszik azonban könnyűnek a következő kérdés, melyet évekkel ezelőtt felvetettem: Legyen adva pont a síkban, melyek nincsenek mind egy körön. Tekintsük az összes köröket, melyek a pontok közül hármon átmennek. Igaz-e, hogy így legalább kört kapunk? Ha pont egy körön van, akkor pontosan kört kapunk. A megfelelő kombinatorikus általánosítás így hangzik: Legyen elem, , az -kból alkotott legalább három elemű halmazok úgy, hogy mindegyik az -kből álló hármas egy és csakis egy -ban fordul elő. Mekkora minimális értéke? ‐ A párok esetén a geometriai és a kombinatorikus probléma megoldása, amint láttuk, ugyanaz volt, minimális értéke mindkét esetben . Valószínű azonban, hogy ternók (három elemű halmazok) esetén minimuma a kombinatorikus esetben kisebb, mint a geometriai problémánál. Hanani bebizonyította a következőt: Adjunk meg tetszőlegesen egy kis pozitív számot; ehhez mindig található egy úgy, hogy ha , és adva van elem, , akkor értéke a kombinatorikus problémánál kielégíti a következő egyenlőtlenséget: Hanani bizonyítása, mely eddig még nem jelent meg nyomtatásban, a következő: Legyen az halmaz elemeinek a száma . Feltehetjük, hogy a halmazokat pl. a bennük levő elemek száma szerint csökkenő sorrendbe rendeztük, tehát Az összes hármasok száma, amiket az elemből képezhetünk, Ezek mindegyike előfordul egy halmazban és csak egyben, viszont az -edik halmazban hármas fordul elő, így | | amiből | | minthogy miatt . Ebből következik (7) abban az esetben, ha Arra az esetre, ha ennél nagyobb érték, gondoljuk meg mindenek előtt, hogy elemei közül egyrészt a többi mindegyike legfeljebb -t tartalmazhat, mert minden hármas csak egy -ben fordul elő, másrészt minden -ben szereplő elempár legalább még egy -ben előfordul, mert különben a kérdéses elempárból és egy -ben nem szereplő elemből álló hármasok egy halmazban sem szerepelnének. Mivel elemeiből pár képezhető, így -en kívül legalább még ennyi halmazunk van: | | Ez abban az esetben adja (7)-et, ha elég nagy, és elég nagy; pl. ha , akkor | | s így teljesül (7), ha elég nagy (pl. ha , tehát . Ha végül akkor vizsgáljuk meg azt is, hány halmazban kell egy -beli elempárnak előfordulnia ahhoz, hogy minden hármas szerepelhessen, amely ebből a párból és még egy, -ben nem szereplő elemből áll. Egy-egy -beli párból számú ilyen hármas alkotható, mert ennyi elem nem szerepel -ben. Másrészt egy -nek, amely két -beli elemet tartalmaz, emellett legfeljebb további eleme lehet, mert nem lehet -nél több eleme. Így ahhoz, hogy egy -beli párt tartalmazó összes hármas előfordulhasson, ennek a párnak -en kívül még legalább halmazban kell előfordulnia. Mivel elemeiből pár alkotható, így
A (8) feltételnek eleget tevő értékek kisebbek -nél, ha , az ilyen -ekre tehát csökkentjük a nyert kifejezés értékét, ha -et nála kisebb számmal helyettesítjük. Eszerint a (8) alatti értékekre (a nyert korlát jobban kezelhető utolsó előtti alakját használva) | |
Ezek szerint a (8) feltételnek eleget tevő értékekre is teljesül (7), amint elég nagy . Az -re adódott korlátok közül a legnagyobbat választva -nak, bármekkora is , mindig teljesül (7), amint . Ezzel Hanani tételét bebizonyítottuk. Hanani azt is bebizonyította, hogy ha , ahol prímszámhatvány, akkor Hanani sejti, hogy itt . (7) és (9)-ből az analitikus számelmélet eszközeivel könnyen belátható, hogy a kombinatorikus problémánál minimumának nagyságrendje , pontosabban minden pozitív -hoz van oly , hogy ha , akkor | | (10) |
(10) bal oldalát már bebizonyítottuk, a jobb oldallal itt nem foglalkozhatunk. E problémákat hármasokról -esekre is általánosíthatjuk minden esetén, de ezzel most nem foglalkozunk.
Erdős Pál
David Hilbert (1862‐1943) a jelenkor egyik legkiválóbb matematikusa, főleg Göttingában működött. S. Cohn-Vossen német geométer, a hitlerizmus miatt emigrált s Leningrádban lett professzor, hol még a harmincas években elhunyt.J. Karamata jugoszláv matematikus, jelenleg a genfi egyetemen professzor. Főleg végtelen sorokra vonatkozó vizsgálatai tették ismertté.L. M. Kelly a Missouri-i egyetemen müködött, jelenleg East Lansingban, Michigan állam egyetemén professzor.J. J. Sylvester (1814‐1897) kiváló angol matematikus, főleg számelmélettel s geometriával foglalkozott, az angliai oxfordi egyetemen, majd a John's Hopkins University-n (Baltimore, USA) működött. Ő alapította az első amerikai matematikai folyóiratot, a most is megjelenő American Journal of Mathematics-et.11851. kérdés, 59. kötet 90. old.H. S. M. Coxeter kiváló kanadai geométer, a torontói egyetem professzora.American Mathematical Monthly 55 (1948) 26-28. oldal.T. S. Motzkin az USA-ban élő izraeli matematikus. Jelenleg Los Angelesben a californiai egyetemen professzor.A. Robinson jelenleg a jeruzsálemi héber egyetemen professzor.-vel (olv. a fölött) jelölik az számot. Ennyi pár alkotható elemből; ugyanis mindegyik elem a többi -gyel állítható párba, de az így megszámlált pár közt mindegyiket kétszer vettük számításba (mindegyik eleménél). A későbbiekben szükségünk lesz az elemből kiválasztható hármasok számára is. Minden elem a tőle különböző elemből alkotható párral összekapcsolva alkothat egy-egy hármast. Ilyen módon hármast számoltunk meg, de minden hármast -szor vettünk tekintetbe, tehát a kiválasztható hármasok száma . Ezt így szokás jelölni: (olv. a fölött).N. G. de Bruijn holland matematikus, munkatársam, kivel több közös cikkem van.G. Dirac magyar származású angol matematikus, a világhírű angol fizikus, P. Dirac fogadott fia.Th. Motzkin, The lines and planes connecting the points of a finite set. Transactions of the American Mathematical Society 70 (1951) 451‐464. Motzkin Gallai tételének érdekes többdimenziós általánosításait is tárgyalja.W. O. J. Moser kanadai matematikus, a manitobai egyetemen, Winnipegben professzor.L. M. Kelly and W. O. J. Moser, On the number of ordinary lines determined by points, Canadian journal of Mathematics, 10 (1958) 210-219.H. Hanani izraeli matematikus, kollégám a haifai műegyetemen.Szekeres György Ausztráliában működő magyar matematikus.Az -k és -k mindig szemléltethetők ilyen (általában nem egyenes) villamosvonalakkal. Ezeknek esetleg a kijelölt pontokon kívül is lesz kereszteződésük, de mi csak a kijelöltekkel foglalkozunk. Ez a sík egy olyan átalakítása, amelynél egy adott kör pontjai helyben maradnak, a kör középpontjának nincs megfelelője, és minden ezen a középponton átmenő kör egy egyenesbe megy át. |