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

3. Az Erdős–Szekeres-tétel

3. Az Erdős–Szekeres-tétel

A következő feladatok szorosan kapcsolódnak Pach János kiváló cikkéhez az Erdős–Szekeres-tételről ugyanebben a kötetben, így ezt a fejezetet az említett cikk után érdemes elolvasni.

3.1. Feladat. Bizonyítsuk be, hogy öt általános helyzetű pont között a síkon mindig van négy, amelyek konvex helyzetben vannak és az ötödik pont nincs a konvex burkukban.

3.2. Feladat. Azt mondjuk, hogy k egyenes konvex helyzetben van, ha egy konvex k -szög oldalegyenesei. Bizonyítsuk be, hogy minden n ? 3 egészhez van olyan f ¯ ( n ) szám, amelyre igaz a következő feltétel. Tetszőleges f ¯ ( n ) általános helyzetű egyenes (nem megy át három egy ponton) között a síkon található n konvex helyzetben.

3. ábra. Hegy és völgy

Segítség: Hasonlóan mint az Erdős–Szekeres-tétel bizonyításában, definiálhatjuk a hegy és völgy fogalmát (3. ábra). Ezek után definiálhatjuk az f ¯ ( k , l ) függvényeket, és ugyanazt a rekurziót bebizonyíthatjuk, mint ami az eredeti Erdős–Szekeres-tétel bizonyításában szerepel az f ( k , l ) függvényre. Az egyetlen különbség az, hogy az eredeti bizonyításban egy olyan pontot kerestünk, ami egyszerre egy hegy utolsó és egy völgy első eleme. Itt viszont olyan egyenest kell találnunk, amely egyszerre első eleme egy hegynek is és egy völgynek is.

3.3. Feladat. (i) Bizonyítsuk be, hogy minden n ? 3 egészhez van olyan h ( n ) szám, amelyre igaz a következő feltétel. Tetszőleges h ( n ) általános helyzetű pont között a síkon vagy van n konvex helyzetben úgy, hogy bármely két pont távolsága legfeljebb egy, vagy van n konvex helyzetben úgy, hogy bármely két pont távolsága legalább egy.

(ii) Bizonyítsuk be, hogy minden n ? 3 egészhez van olyan h ' ( n ) szám, amelyre igaz a következő feltétel. Tetszőleges h ' ( n ) általános helyzetű pont között a síkon vagy van n konvex helyzetben úgy, hogy bármely két pont távolsága legfeljebb egy, vagy van n konvex helyzetben úgy, hogy bármely két pont távolsága legalább 2.

Segítség: (i) Használjuk először a Ramsey-tételt, utána pedig az Erdős–Szekeres-tételt. Színezzük ki a pontok közötti éleket két színnel: pirossal, ha a két pont messzebb van mint 1; kékkel, ha közelebb. (Ha éppen 1 a távolság, akkor bármelyik színt használhatjuk.) Ha elég sok pontból indulunk ki, lesz egy nagy részhalmaz, ahol az összes él ugyanolyan színű. Ezekre a pontokra alkalmazzuk az Erdős–Szekeres-tételt.

(ii) Most színezzük ki a pontok közötti éleket három színnel: pirossal, ha a két pont messzebb van mint 2; kékkel, ha közelebb mint 1; és zölddel, ha a távolság 1 és 2 között van. Ha elég sok pontból indulunk ki, lesz egy nagy részhalmaz, ahol az összes él ugyanolyan színű. Ha ez a szín piros vagy kék, akkor ezekre a pontokra alkalmazzuk az Erdős–Szekeres-tételt. A zöld esetet azzal az észrevétellel zárhatjuk ki, hogy nem lehet 25-nél több pont úgy, hogy az összes köztük futó él zöld.

Megjegyezzük, hogy a feladatban a 2 helyére tetszőleges számot írhatunk.

3.4. Feladat. Bizonyítsuk be, hogy hat általános helyzetű pont között a térben mindig van öt amelyek konvex helyzetben vannak.

3.5. Feladat. Bizonyítsuk be, hogy minden ? //>// 0 -hoz van olyan N hogy N pont között a síkon mindig található három, amelyek egy ? és ? - ? közötti szöget határoznak meg.

Segítség: Ha van három pont egy egyenesen, akkor készen vagyunk. Ha a pontok általános helyzetben vannak, akkor elég nagy N esetén található n ? 2 ? ? pont konvex helyzetben. Ennek a konvex sokszögnek valamelyik három szomszédos csúcsa eleget tesz a feltételnek.