Feladat: 1971. évi Kürschák matematikaverseny 2. feladata Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Bajmóczy Ervin ,  Berényi Péter ,  Füredi Zoltán ,  Komjáth Péter ,  Máté András ,  Móri Tamás ,  Ruzsa Imre 
Füzet: 1972/február, 52 - 56. oldal  PDF  |  MathML 
Témakör(ök): Ponthalmazok, Sík geometriája, Négyszögek geometriája, Egyéb sokszögek geometriája, Halmazok számossága, Kombinatorikus geometria síkban, Maradékos osztás, Pont körüli forgatás, Kürschák József (korábban Eötvös Loránd)
Hivatkozás(ok):Feladatok: 1972/február: 1971. évi Kürschák matematikaverseny 2. feladata

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.

A feladat követelményei szerint három dolgot kell szem előtt tartanunk: minden pontot csak egy másikkal köthetünk össze, a metszéspontoknak a szakaszokra kell esniük és nem szabad egybeesniük.
Két metsző szakasz végpontjainak a kiválasztása ugyanaz a feladat, mint egy konvex négyszög csúcsaié, mert konvex négyszög átlói egymást metsző szakaszok és két egymást metsző szakasz végpontjai konvex négyszög csúcsai, amelyiknek a szakaszok az átlói.
Megemlítjük még a ponthalmaz konvex burkának a fogalmát, aminek segítségével könnyebben tudjuk magunkat kifejezni. Ezen azt a legszűkebb konvex tartományt értjük, amelyik az összes pontot tartalmazza. Ezt szemléletesen úgy képzelhetjük el, hogy a pontokban a síkra merőleges tűket gondolunk, majd egy gumikarikát kihúzunk akkorára, hogy az összes tű belül legyen rajta és elengedjük. Az összeugró gumi által körülzárt tartomány a konvex burok. Ez véges ponthalmaz esetén konvex sokszög, aminek a csúcsai a ponthalmaz pontjai közül valók.

 
I. megoldás. Fel fogjuk használni, hogy 5 pont közül a síkban mindig kiválaszthatók egy konvex négyszög csúcsai, ha nincs köztük 3 egy egyenesen levő pont.
Valóban, ha az 5 pont konvex burka ötszög, akkor bármelyik 4 pont megfelel. Ha négyszög a konvex burok (amelyik a belsejében tartalmaz még egy pontot), akkor is rendelkezésünkre áll már egy konvex négyszög. Ha a konvex burok háromszög, a belsejében 2 ponttal, akkor húzzuk meg az utóbbiakon átmenő egyenest (3. ábra). Ez 2 oldalt a belsejében metsz, mert csúcson nem mehet át, ugyanis nincs 3 pont egy egyenesen. Ekkor a harmadik oldal végpontjai és a két belső szögpont alkot konvex négyszöget.
 
 

3. ábra
 

Válasszunk egy e egyenest, amelyik nem párhuzamos semelyik két ponton átmenő egyenessel. Ez lehetséges, mert véges sok pont csak véges sok irányt határoz meg. Helyezzünk el egy e-vel párhuzamos egyenest úgy, hogy a ponthalmaz az egyik partjára essék, majd mozgassuk, irányát megtartva, a pontrendszer irányában és jelöljük meg 4 helyzetét, az elsőt úgy, hogy 5 pont kerülön át az egyenes ellenkező partjára, majd következő hármat úgy, hogy 4‐4 újabb pont kerüljön át a másik oldalra. Ekkor még 5 pont marad az első parton.
Az első 5 pont közül ki tudjuk választani két metsző szakasz végpontjait és marad még egy pont, ezt vegyük a következő négyhez és ismét válasszuk ki két metsző szakasz végpontjait. A fennmaradó ponttal ismételjük az eljárást és folytatjuk, amíg mindegyik pontcsoportot fel nem használjuk.
Így 5 szakaszpárt választottunk ki. Ezek kiválasztásuk szerint egymást metsző szakaszokból állnak és nincs kettőnek közös végpontja. A metszéspontok is mind különbözők, mert mindegyik szakaszpár négy végpontja közül legalább hármat, s így az egyik szakasz mindkét végpontját, egy
e-vel párhuzamos egyenes elválaszt a korábban kiválasztott szakaszoktól, tehát a szakasz belsejében levő metszéspontot is elválasztja a korábban nyert metszéspontoktól.
Ezzel a feladat állítását igazoltuk.
 
Megjegyzések. 1. Az eljárás csak 21 pontot használt fel az 5 metszéspont létrehozásához, a huszonkettedik csak ahhoz kellett, hogy a párokba állítás lehetséges legyen. Ugyanez az eljárás általában 4n+1 szögpontból n különböző metszéspont létrehozását teszi lehetővé.
2. Többen úgy választották meg a 3 síksávot és 2 félsíkot, hogy a ponthalmazból 5‐5‐5‐5, ill. 2 pontot tartalmazzanak. Ekkor utolsó lépésben az első 4 metszéspont kiválasztásakor fennmaradt pontok és az utolsó két pont közül lehet még egy metsző szakaszpár P, Q és R, S végpontjait kiválasztani. Tegyük fel, hogy ezek metszéspontja egybeesik egy másik szakaszpár pl. AB és CD metszéspontjával (4. ábra). Ekkor az előbbi pár legalább egyik szakaszának mind a két végpontja másik síkrészben van, mint a metszéspont.
 
 

4. ábra
 

Ha RS ilyen szakasz, akkor ez metszi az ACBD négyszög két szemben fekvő oldalát, mondjuk AC-t és BD-t, tehát ezek a szakaszok és RS két különböző metszéspontot szolgáltatnak. Ezek különböznek a további metszéspontokból is, mert ugyanabban a síkrészben vannak, mint az eredeti metszéspont (ami különben továbbra is létrejön mint az eddig még figyelmen kívül hagyott PQ metszéspontja RS-sel).
3. Ahelyett, hogy párhuzamos egyenesekkel osztanók csoportokba a pontokat, kiválaszthatjuk a ponthalmaz konvex burkának egy A csúcsát és ezen át egy egyenest, amelyiknek egyik partjára esik a ponthalmaz minden A-tól különböző pontja; ezután ennek egyik félegyenesét forgatva hozunk létre olyan szögtartományokat, amelyek 4‐4‐4‐4 pontot tartalmaznak A-n kívül, és A-val és az első 4 ponttal kezdve végezzük a fenti kiválasztási eljárást. A forgó félegyenes egyenként halad át a pontokon, mert három pont nem esik egy egyenesre.
 
II. megoldás. Újabb eljárást adunk meg legalább 5 pont esetén olyan metsző szakaszpár kiválasztására, amelyek metszéspontja nem eshet rá egyetlen további (esetleg) kiválasztható szakaszra sem.
Legyen a ponthalmaz konvex burkának három szomszédos csúcsa A, B és C. Ekkor az ABC konvex szögtartomány (hozzáértve a határoló félegyeneseket is) tartalmazza a ponthalmazt.
Tekintsük a B elhagyásával maradó ponthalmaz K konvex burkát. Ez is konvex sokszög, mert legalább 4 nem egy egyenesen levő pontot burkol. K határának egyik, A-tól C-ig haladó törött vonala elválasztja a halmaz legalább egy pontját B-től, kivéve ha ez a határ az AC szakaszból és egy az ABC háromszögben futó, A-t és C-t összekötő törött vonalból áll, amelyiknek az összes további pont szögpontja (5. ábra).
 
 

5. ábra
 

Utóbbi esetben vegyük fel pl. K-nak A-val szomszédos, D, E, F csúcsait (F azonos lehet C-vel) és válasszuk ki az AE és DF szakaszt. Ezek metszéspontja az AF egyenesnek azon a partján jön létre, amelyiken B van. A ponthalmaz többi pontja (ha van további pont) az egyenes másik partján van, így minden esetleges további szakaszpár négy végpontja közül legalább 3 az utóbbi parton van, tehát az egyik szakasz is és ha a szakaszok metszik egymást, akkor a metszéspontjuk is.
Abban az esetben, ha van a ponthalmaznak olyan D pontja, amire BD metszi K határát, akkor legyen EF az az oldal, amit átmetsz (6. ábra). Nem mehet át BD valamely csúcson, mert nincs 3 egy egyenesre eső pont a halmazban. Ekkor a halmaz minden további pontja az EF egyenes egyik partján van, a határán sem lehet, így egyetlen további szakaszpár metszéspontja sem eshet egybe BD és EF metszéspontjával.
 
 

6. ábra
 

22 (sőt már 21) pontból kiindulva, az eljárást 5-ször ismételhetjük, s így 5 különböző metszéspontot tudunk létrehozni; általában 4n+1 pontból n metszéspontot.
 
Megjegyzés. 5 pont esetén újabb bizonyítást nyertünk arra az I. megoldásban felhasznált segédtételre, hogy 5 pont közül mindig kiválaszthatók egy konvex négyszög csúcsai.
 
III. megoldás. A ponthalmaz meghatározta összes szakaszok metszéspontjai közül fogunk olyat kiválasztani, amelyiken legfeljebb 3 szakasz megy át. Megmutatjuk, hogy a szakaszok összes metszéspontjai konvex burkának a csúcsai ilyenek.
Világos, hogy ezzel a feladat állítása bizonyítást nyer, ugyanis ha legalább 5 pont van adva, akkor az előző megoldásokban bizonyított segédtétel szerint legalább egy metszéspont is van. Kiválasztjuk a metszéspontok konvex burkának egy csúcsát és 2 olyan szakasz végpontjait, amelyeknek ez a metszéspontja. A maradó pontokkal addig ismételhetjük az eljárást, amíg legalább 5 pont marad, tehát 21 ponttal még 4-szer, általában 4n+1 ponttal n-szer.
A keletkező metszéspontok mind különbözők, mert 2‐2 metsző szakasz közül legfeljebb az egyik mehet át korábban kiválasztott szakaszpárok metszéspontján.
A kimondott állítást indirekt úton bizonyítjuk. Ha a metszéspontok konvex burkának egy P csúcsán át legalább 4 szakasz menne át, akkor vegyük ezeknek egy-egy, a konvex burkon kívül eső végpontját. Ezek és P közül kiválaszthatók két egymást metsző szakasz végpontjai. Ezek metszéspontja a metszéspontok halmazán kívül van és metszéspontja a ponthalmaz 4 pontja által meghatározott szakaszoknak. Valóban, vagy P nem is szerepel a kiválasztott 4 pont közt, vagy ha igen, akkora benne végződő szakasz része egy, a ponthalmaz pontjai által meghatározott szakasznak (7. ábra).
 
 

7. ábra
 

Ezzel ellentmondásra jutottunk a konvex burok fogalmával, így P-n nem mehet át 4 szakasz.
 
Megjegyzések. 1. Nem nehéz látni, hogy 3 szakasz sem mehet át a metszéspontok konvex burka határán levő metszéspontokon. Ennek bizonyítását az olvasóra bízzuk.
2. Felvetődik a kérdés, hogy 5 metszéspont létrehozására nem elegendő-e 21-nél kevesebb pont is, ill. hogy nem lehet-e bármilyen 21 pontból kiindulva 5-nél több metszéspontot is létrehozni.
Valóban, a megoldások egymástól lehetőleg elválasztott szakaszpárok kiválasztása útján biztosítják a metszéspontok különbözőségét, viszont sok metszéspont akkor keletkezik, ha egy-egy szakaszt minél több másik metsz. Erre utal az I. megoldáshoz fűzött 2. megjegyzés is.
Másfelől talán az is váratlan első pillanatra, hogy 7 pont még nem föltétlenül teszi lehetővé 2 metszéspontot létrehozó, közös végpont nélküli szakaszok kiválasztását. Erre a 8. ábra két példát is mutat.
 
 

8. ábra
 

A megoldások 9 pont esetén biztosítják 2 metszéspont létrehozását. A lehetséges esetek megfelelő csoportosításával és végigvizsgálásával belátható, hogy már 8 pont közül is mindig kiválaszthatók 2 különböző metszéspontot szolgáltató, közös végpont nélküli szakaszok végpontjai.
Ebből következik, hogy 5 metszéspont létrehozására már 20 pont is elegendő és általában n metszéspont létrehozására 4n pont. Valóban, 3 ‐ általában n-2 ‐ metszéspont létrehozására alkalmazhatjuk bármelyik megoldás eljárását, és az utolsó 8 pont közül kiválaszthatók még további 2 metszéspontot adó szakaszok végpontjai.
Az elmondottak részleteire és további megjegyzésekre külön cikkben térek vissza.