Cím: Néhány elemi geometriai problémáról
Szerző(k):  Erdős Pál 
Füzet: 1980/október, 49 - 54. oldal  PDF  |  MathML 
Témakör(ök): Szakmai cikkek

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. 1962-ben e folyóiratban publikáltam egy azonos című cikket.* E cikkre mint I-re fogok hivatkozni. E cikkben hasonló természetű problémákkal fogok foglalkozni, de elsősorban néhány I-ben felvetett problémához kell megjegyzéseket fűznöm.
I-ben a következő, Sylvestertől származó problémát említettem: Legyen adva n pont, P1,...,Pn a síkban. Maximálisan hány olyan egyenes lehetséges, mely e pontok közül pontosan hármon megy át? E probléma még most sincs teljesen megoldva, de Burr, Grünbaum és Sloane* egy nemrég megjelent cikkükben sok érdekes eredményt értek el és Sylvester eredményeit messzemenően élesítették.
Sylvester problémájával kapcsolatban I-ben a következő kérdést vetem fel: Mekkora azon egyenesek maximális száma, amelyek az n pont közül pontosan 4-en (illetve általában k-n) mennek át? Azt sejtettem, hogy ez a maximum sokkal kisebb rendű, mint n2 és talán kisebb, mint cn. Elsősorban Crofttal észrevettük, hogy a síkrács pontjai mutatják, hogy meg lehet adni a síkban n pontot úgy, hogy azon egyenesek száma, amelyek e pontok közül pontosan k-n mennek át, nagyobb, mint ckn2, ahol ck k-tól függő állandó. ck pontos értéke nem ismeretes, és Crofttal sejtjük, hogy minden ε>0-hoz van olyan k0=k0(ε), melyre minden k>k0 esetén ck<ε/k2. Ha viszont feltesszük, hogy P1,...,Pn olyan, hogy nincs közülük k+1 egy egyenesen, akkor valószínűleg tényleg igaz, hogy azon egyenesek száma, melyek közülük k-n mennek át, sokkal kisebb rendű, mint n2. Kárteszi* bebizonyította, hogy ezen egyenesek száma nagyobb lehet, mint cknlogn és ezt Grünbaum ckn1+1/k-ra élesítette. Nem lehetetlen, hogy Grünbaum eredménye már közel van ahhoz, hogy éles legyen. Egyelőre azonban még a következő egyszerű kérdésre sem tudjuk a választ: Igaz-e, hogy minden ε>0-hoz van olyan n0, hogy ha n>n0 és P1,...,Pn n olyan pont (a síkban), melyek közül nincs öt egy egyenesen, akkor azon egyenesek száma, melyek négy Pi-n mennek át, kisebb, mint εn2.
Elliott* bebizonyította, hogy ha n>393 és a síkban adva van n pont, melyek nincsenek mind egy körön, akkor ezek legalább (n-12) kört határoznak meg. Ezzel egy enyhén módosított formában bebizonyította I-ben kimondott sejtéseim egyikét. ((n-12) az (n-12)+1-gyel helyettesíthető, ha azt az egyenest, mely n-1 ponton megy át, végtelen sugarú körnek tekintjük.) Az n>393 valószínűleg lényegesen javítható.

 

2. Corrádi, Hajnal és én sejtettük, hogy ha P1...,Pn n pont a síkban, melyek nincsenek mind egy egyenesen, akkor ezek legalább n-2 különböző szöget határoznak meg (a szögek ≥0 és ≤π-nek veendők). Ha még feltesszük, hogy a pontok között nincs három egy egyenesen, akkor egészen egyszerű bebizonyítani, hogy a pontok valóban n-2 különböző szöget határoznak meg, és a szabályos sokszög mutatja, hogy n-2 pontos. Sajnos azonban az általános esetben semmi elfogadható alsó becslésünk nincs ‐ például azt sem tudtuk eddig bebizonyítani, hogy legalább n/2 különböző szöget határoznak meg. E kérdés elintézéséért 1000 forint jutalmat adok.
 

3. 1932-ben Klein Eszter észrevette, hogy ha öt pont van adva a síkban és nincs három egy egyenesen, akkor ezen öt pontból mindig kivehető négy, melyek egy konvex sokszög csúcsai. Az egyszerű bizonyítást az olvasóra hagyjuk. Klein Eszter továbbá kérdezte: Van-e olyan f(n), hogy ha a síkban adva van f(n) pont, melyek közül semelyik három sincs egy egyenesen, akkor mindig kivehető közülük n pont, melyek egy konvex sokszög csúcsai? Szekeres hamarosan sejtette, hogy f=2n-2+1. Szekeressel bebizonyítottuk, * hogy
2n-2+1≤f(n)≤(2n-4n-2).
Makai Endre és Turán Pál bizonyította, hogy f(5)=9, de egyelőre f(6)=17 nincs meg.
E problémát én happy end problem-nek neveztem, ugyanis Klein Eszter "behálózta'' Szekeres Györgyöt és boldogan élnek Sydney-ben ‐ jelenleg (1980. augusztus) Pesten tartózkodnak.
Mikor 1977-ben meglátogattam Szekereséket, a probléma következő változata jutott eszembe: Létezik-e olyan F(n), hogy ha a síkban adva van F(n) pont, P1,...,PF, melyek közül semelyik három nincs egy egyenesen, akkor kiválasztható-e közülük n pont, melyek olyan konvex n-szöget határoznak meg, mely egyetlen Pi-t sem tartalmaz a belsejében? Azonnal adódik f(4)=5-ből, hogy F(4)=5 (az egyszerű bizonyítást az olvasóra bízom). De már F(5) létezését nem tudtam bizonyítani. Ehrenfurt bebizonyította, hogy F(5) létezik, és Harborth* bebizonyította, hogy F(5)=10. Egyelőre nem tudjuk, hogy F(6) létezik-e. Ugyanis könnyen elképzelhető, hogy minden n-re megadható n pont, P1...Pn a síkban úgy, hogy nincs három egy egyenesen és a Pi-k közül bármely 6 vagy nem alkot konvex hatszöget, vagy ha a hatszög konvex, akkor belsejében van legalább egy másik Pi.
Az F(6)-ról való kérdés megoldására 1000 forint jutalmat tűzök ki, F(n) létezésének bizonyításáért 3000 forintot.
Szekeressel bizonyítottuk,* hogy ha a síkban adott 2n pont, akkor azok mindig meghatároznak egy szöget, mely nagyobb, mint π(1-1/n). E tétel meglepően éles, mert Szekeres egy régebbi tétele* szerint minden ε>0-hoz van 2n pont úgy, hogy e pontok által meghatározott szögek mind kisebbek, mint π(1-1/n)+ε. Első pillanatban azt gondolhatnánk, hogy e tétel annyira éles, hogy további javításra nincs lehetőség. Lehetséges azonban, hogy már 2n-nél kevesebb pont is biztosít π(1-1/n)-nél nagyobb szöget. Bizonyítani csak annyit tudunk, hogy már 2n-1 pont is biztosít egy szöget, mely nagyobb vagy egyenlő, mint π(1-1/n). Nem lehetetlen azonban, hogy ha n>n0, akkor már 2n-1+1 pont is biztosít egy szöget, mely nagyobb, mint π(1-1/n).
 

4. Jelölje d(P,Q) a P és Q pontok távolságát. Anning és én még 1945-ben bizonyítottuk,* hogy ha P1, P2, ... végtelen sok pont a síkban úgy, hogy d(Pi,Pj) minden 1≤i<j számpárra egész szám, akkor pontjaink egy egyenesen vannak. Első bizonyításunk nem volt egész egyszerű, de néhány hónap múlva a következő meglepően egyszerű bizonyítást találtam: Ha pontjaink nincsenek mind egy egyenesen, akkor az általánosság rovása nélkül feltehetjük, hogy P1, P2, P3 nincsenek egy egyenesen. Legyenek X1, X2, ..., Xk olyan pontok, melyekre d(Xi,P1), d(Xi,P2), d(Xi,P3), mind egész számok. Bebizonyítjuk, hogy ekkor
k≤4(d(P1,P2)+1)(d(P1,P3)+1).(1)
(1)-ből Anninggel közös tételünk azonnal következik. (1) bizonyítása viszont rendkívül egyszerű. Legyen X olyan pont, melynek távolsága a P1, P2, P3 pontoktól egész szám. A háromszög egyenlőtlenség miatt
|d(X,P1)-d(X,P2)|≤d(P1,P2),
és ezért X d(P1,P2)+1 darab olyan hiperbola valamelyikén van, melyeknek fókusza P1 és P2 (ugyanis minthogy |d(X,P1)-d(X,P2)| egész és nem nagyobb, mint d(P1,P2), legfeljebb d(P1,P2)+1 különböző értéket vehet fel). Hasonlóan adódik, hogy X legfeljebb d(P1,P3)+1 olyan hiperbolán van, melyeknek fókuszai P1 és P3. Minthogy P1, P2, P3 nincsenek egy egyenesen, két hiperbola, melyeknek fókuszai P1, P2, illetve P1, P3, legfeljebb négy pontban metszik egymást. Ebből viszont azonnal nyerjük, hogy az X pont választására legfeljebb 4(d(P1,P2)+1)⋅(d(P1,P3)+1) lehetőség van, s ezzel (1) be van bizonyítva.
Tudtommal senki sem vizsgálta, vajon az (1) egyenlőtlenség javítható e és ha igen, mennyire.
Legyen P1, P2, ... végtelen sok pont a síkban, melyek közül nincs három egy egyenesen. Két ilyen pontot összekötünk egy éllel, ha távolságuk egész szám. Hogyan jellemezhetőek az így nyert gráfok? Előbbi bizonyításunk adja, hogy e gráf nem tartalmazhat egy K(3,α0) részgráfot, azaz nem lehet benne három szögpont X1, X2, X3 és végtelen sok más szögpont Y1, Y2, ..., melyek mindegyike az Xi-kel össze van kötve. Nem sikerült eldöntenem, hogy e szükséges feltétel elégséges-e. Az biztos, hogy gráfunk minden n-re tartalmazhat egy n szögpontú teljes gráfot. Nem világos azonban, hogy minden n szögpontú gráf beágyazható gráfunkba (azaz van P1,...,Pn pont úgy, hogy d(Pi,Pj) akkor és csakis akkor egész szám, ha Pi és Pj a gráfunkban össze van kötve).
Nagyon érdekes problémára jutunk, ha még azt is feltesszük, hogy négy Pi nem lehet egy körön. Harborth és mások is bebizonyították, hogy megadható öt pont általános helyzetben (azaz nincs négy egy körön és három egy egyenesen) úgy, hogy bármely kettő távolsága egész szám. Nem ismeretes azonban, hogy megadható-e hat ilyen tulajdonságú pont. Nem lehetetlen, hogy minden n-re megadható n ilyen pont. Ulam a következő problémát vetette fel: Van-e a síkban egy mindenütt sűrű ponthalmaz, melyre bármely két pont távolsága racionális szám? (Egy ponthalmaz mindenütt sűrű, ha minden kör belsejében van pontja.) Ulam kérdésére a válasz valószínűleg tagadó, de ennek bizonyítása nem látszik könnyűnek. Ismeretes, hogy van olyan r, melyre az r sugarú körön megadható egy mindenütt sűrű ponthalmaz úgy, hogy bármely két pont távolsága racionális. Valószínűnek látszik, hogy ha S egy zárt ponthalmaz a síkban (vagyis S minden konvergens pontsorozatával együtt annak határértékét is tartalmazza), melyre van olyan S1⊂S, mely S-ben mindenütt sűrűn van és S1 bármely két pontjának távolsága racionális, akkor ez csak nagyon speciális S halmazokra lehetséges. Biztosra veszem, hogy ez akkor is igaz marad, ha nem ragaszkodunk az S1⊂S feltételhez és csak azt kívánjuk, hogy S1 minden sűrűsödési pontja S-ben legyen. Tudtommal e kérdéseket még nem vizsgálták.
Végül még egy kérdést említek. Legyen adva n pont, P1 ..., Pn a síkban általános helyzetben (azaz nincs három egy egyenesen és négy egy körön). Tekintsük a d(Pi,Pj), 1≤i<j≤n számokat. Lehetséges, hogy e távolságok között n-1 különböző legyen és az i-edik távolság (n-i)-szer forduljon elő?
 
 

n=3-ra e feltétel teljesül, ha a P1P2P3 háromszög egyenlő szárú, n=4-re, ha P4 az egyenlő szárú háromszög körülírt körének középpontja. Azt gondoltam, hogy n≥5-re ez már nem lehetséges, de C. Pomerance n=5-re a következő példát találta: P1 az r sugarú kör középpontja, d(P1,P2)=d(P1,P3)=d(P2,P3)=r, P4 a P1P2P3 háromszög körülírt körének középpontja, P5 a P3P4 felező merőlegesének az r sugarú körrel való metszéspontja. Könnyű belátni, hogy ez az 5 pont általános helyzetű és a feltételeinket kielégíti. Az r távolság 4-szer fordul elő, d(P1,P4) háromszor, d(P3,P5)=d(P4,P5). Talán n≥6-ra már tényleg igaz, hogy nincs ilyen tulajdonságú pontrendszer, de e kérdést egyelőre nem tudom eldönteni.
Még két megjegyzést szeretnék ehhez a problémához fűzni. Megkövetelhetnénk, hogy három P ne legyen egy egyenesen, négy egy körön és ne legyen olyan kör, melynek középpontja egy adott P és amely három másik P-t tartalmaz. n=4-re könnyű négy ilyen pontot találni, melyre az i-edik távolság (i=1,2,3) (n-i)-szer fordul elő, de n=5-re ez nem sikerült, és nem tudom, 5 ilyen pont van-e.
Legyen P1, ..., Pn általános helyzetben, nem tudom, hogy legalább hány különböző távolságot határoznak meg. Továbbá kérdezhetjük, hogy ha P1, ..., Pn nem tartalmaz egyenlő szárú háromszöget (azaz minden i-re a d(Pi,Pj), j=1,2,...,n, j≠i távolságok mind különbözőek), akkor legalább hány különböző távolság fordul elő a d(Pi,Pj), 1≤i<j≤n számok között? A választ erre a kérdésre nem ismerjük.
 

5. Legyenek P1, ..., Pn egy konvex n-szög csúcsai. Sejtettem és Altman bebizonyította, hogy a d(Pi,Pj) távolságok között legalább [n/2] különböző van. Egyenlőség áll például a szabályos n-szög esetén.
Továbbá sejtettem, hogy mindig van egy pont, Pi, hogy a d(Pi,Pj)j=1,2,...,n, j≠i távolságok közül is van legalább [n/2] különböző. E sejtés még nincs eldöntve. Továbbá sejtettem, hogy van egy Pi pont, melytől nincs három másik Pj egyenlő távolságban. E sejtésből az előbbi sejtések könnyen következnének, de legnagyobb meglepetésemre Danzer e sejtést megcáfolta. Erre sejtettem, hogy van olyan Pi, melytől nincs négy másik P egyenlő távolságban. Danzer ellenpéldája itt már nem működik, de még ha e sejtés igaz is lenne, az már nem következne, hogy van olyan Pi, melytől legalább [n/2] különböző távolság van.
Legyen g(n) az a legnagyobb szám, melyre bárhogyan is adunk meg különböző P1, ..., Pn pontot a síkban, ezek legalább g(n) különböző távolságot határoznak meg. g(n) meghatározása, sőt jó megbecslése rendkívül nehéz feladatnak látszik. Fennáll a következő becslés:
c1n2/3<g(n)<c2⋅n(logn)1/2.(2)
A felső határ (2)-ben tőlem származik, az alsó határ L. Mosertől.* Úgy gondolom, hogy a felső határ közelebb van az igazsághoz, mint az alsó és talán g>c3⋅n(logn)-1/2.
Sajnos e kérdés eldöntése reménytelennek látszik, és 104 forintot tűzök ki a kérdés tisztázására.
Sejtettem, hogy minden k-hoz van olyan ε>0, melyre ha P1,...,Pn olyan pontrendszer, mely εn-nél kevesebb különböző távolságot határoz meg, akkor van k olyan Pi, melyek egy egyenesen vannak. E sejtésre Szemerédi Endre egy meglepően szellemes és egyszerű bizonyítást adott.* Továbbá Szemerédi sejti Altman tételének a következő élesítését: Legyen P1, ..., Pn n pont a síkban úgy, hogy semelyik három nincs egy egyenesen. Ekkor e pontok legalább [n/2] különböző távolságot határoznak meg. Szemerédi bizonyítása azonban csak [n/3]-at ad [n/2] helyett. Próbálják bebizonyítani [n/3]-at és ha tudják, élesítsék ezt az eredményt.
 
 

6. Befejezésül még két problémát említek. E. Straus tavaly bebizonyította, hogy ha az egységkörben adva van egy O pont és három tetszőleges húr, P1P2, P3P4, P5P6, melyek az O ponton átmennek, akkor d(P1,P3)+d(P5,P2)+d(P4,P6)<4. Könnyű belátni, hogy 4 nem helyettesíthető kisebb számmal. Straus bizonyítása trigonometriát és elemi analízist használt, nem sikerült e tételre egy szintetikus geometriai bizonyítást találni ‐ talán valamelyik olvasó ötletesebb, szerencsésebb lesz.
Könnyű belátni, hogy ha P1, ..., Pn egy konvex n-szög csúcsai, akkor a PiPj átlók (n4) metszéspontot határoznak meg a konvex sokszög belsejében. Jelentse h(n) azt a legnagyobb számot, amelyre a PiPj(1≤i<j≤n) átlók legalább h(n) különböző pontot határoznak meg. Határozzák meg h(n)-et a lehető legnagyobb pontossággal. Biztosra veszem, hogy tetszőleges ε>0-hoz van olyan n0, hogy ha n>n0, akkor h(n)≤(1+ε)(n4). Nem vagyok biztos, hogy ez utóbbi probléma tőlem származik-e vagy olvastam valahol.
 
*
 
A problémákat bárki megoldhatja. A megoldásokat a következő címre kérjük:
 Erdős Pál
 MTA Matematikai Kutató Intézet
 Budapest, Reáltanoda u. 13-15. 1053.
*Erdős Pál, Néhány elemi geometriai problémáról, Középiskolai Matematikai Lapok 24. (1062) 193‐201. és Megjegyzések a "Néhány elemi geometriai problémáról'' című cikkhez, 26. (1963) 1‐2.

*S. Burr, B. Grünbaum és Sloane, The orchard problem. S. Burr munkatársam a New York-i City College-ben professzor. B. Grünbaum szintén munkatársam, az University of Washingtonban (Seattle) professzor. Sloane a Bell Laboratories matematikai osztályán munkatárs.

*Kárteszi Ferenc, Sylvester egy tételéről és Erdős egy sejtéséről, Középiskolai Matematikai Lapok, 25. (1963) 3‐9.

*P. D. T. A. Elliott, On the number of circles determined by n points, Acta Math. Sci. Hungar. 18. (1967) 181‐188. ‐ Elliott a Boulder University of Colorado-ban professzor, angol matematikus, munkatársam, fő területe az additív számelméleti függvények.

*P. Erdős and G. Szekeres, A combinatorial problem in geometry, Compositio Math. 2 (1935) 463‐470.

*H. Harborth, Konvexe Fünfecken in ebenen Punktmengen, Elemente der Math. 33 (1978) 116‐118.

* P. Erdős and G. Szekeres, On some extremum problems in elementary Geometry, Ann. Univ. Sci. Budapest 3‐4 (1961) 53‐62.

*G. Szekeres, On an extremum problem in the plane, Amer. J. Math. 63 (1941) 208‐210.

*P. Erdős and A. Anning, Integral distances, Bull. Amer. Math. Soc. 51 (1945) 548‐560. és P. Erdős, Integral distances, ugyanott 966. ‐ Anning Ann Arborban (University of Michigan) volt matematikus, már 30 éve elhunyt.

* P. Erdős, On sets of distances of n points, Amer. Math. Monthly 53 (1946) 248‐250.; L. Moser, On the different distances determined by n points, ugyanott 59 (1952) 85‐91. ‐ L. Moser kanadai matematikus, munkatársam és jó barátom, ki sajnos idő előtt 1970-ben elhunyt.

*Szemerédi tételének bizonyítását lásd P. Erdős, On some problems of elementary and combinatorial geometry, Annali di Mat. Ser IV. 103 (1975) 99‐108. E cikk sok más problémát és eredményt is tartalmaz. Egy valamivel kisebb, de magyar nyelvű cikkre is hivatkozhatom: Erdős Pál, Néhány geometriai problémáról, Mat. Lapok, 8 (1957) 86-92. A legújabb ilyen típusú cikkem: P. Erdős, Some combinatorial problems in geometry, Lecture Notes in Math. 792, Geametry and Diff. Geometry, Proc. Haifa, Israel (1979) 46─53.