|
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 pont közül a síkban mindig kiválaszthatók egy konvex négyszög csúcsai, ha nincs köztük egy egyenesen levő pont. Valóban, ha az pont konvex burka ötszög, akkor bármelyik 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 ponttal, akkor húzzuk meg az utóbbiakon átmenő egyenest (3. ábra). Ez oldalt a belsejében metsz, mert csúcson nem mehet át, ugyanis nincs 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 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 -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 helyzetét, az elsőt úgy, hogy 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 pont marad az első parton. Az első 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 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 -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 pontot használt fel az 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 szögpontból különböző metszéspont létrehozását teszi lehetővé. 2. Többen úgy választották meg a síksávot és félsíkot, hogy a ponthalmazból 5‐5‐5‐5, ill. pontot tartalmazzanak. Ekkor utolsó lépésben az első metszéspont kiválasztásakor fennmaradt pontok és az utolsó két pont közül lehet még egy metsző szakaszpár , és , végpontjait kiválasztani. Tegyük fel, hogy ezek metszéspontja egybeesik egy másik szakaszpár pl. és 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 ilyen szakasz, akkor ez metszi az négyszög két szemben fekvő oldalát, mondjuk -t és -t, tehát ezek a szakaszok és 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 metszéspontja -sel). 3. Ahelyett, hogy párhuzamos egyenesekkel osztanók csoportokba a pontokat, kiválaszthatjuk a ponthalmaz konvex burkának egy csúcsát és ezen át egy egyenest, amelyiknek egyik partjára esik a ponthalmaz minden -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 -n kívül, és -val és az első 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 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 , és . Ekkor az konvex szögtartomány (hozzáértve a határoló félegyeneseket is) tartalmazza a ponthalmazt. Tekintsük a elhagyásával maradó ponthalmaz konvex burkát. Ez is konvex sokszög, mert legalább nem egy egyenesen levő pontot burkol. határának egyik, -tól -ig haladó törött vonala elválasztja a halmaz legalább egy pontját -től, kivéve ha ez a határ az szakaszból és egy az háromszögben futó, -t és -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. -nak -val szomszédos, , , csúcsait ( azonos lehet -vel) és válasszuk ki az és szakaszt. Ezek metszéspontja az egyenesnek azon a partján jön létre, amelyiken 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 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 pontja, amire metszi határát, akkor legyen az az oldal, amit átmetsz (6. ábra). Nem mehet át valamely csúcson, mert nincs egy egyenesre eső pont a halmazban. Ekkor a halmaz minden további pontja az egyenes egyik partján van, a határán sem lehet, így egyetlen további szakaszpár metszéspontja sem eshet egybe és metszéspontjával.
6. ábra (sőt már ) pontból kiindulva, az eljárást -ször ismételhetjük, s így különböző metszéspontot tudunk létrehozni; általában pontból metszéspontot.
Megjegyzés. pont esetén újabb bizonyítást nyertünk arra az I. megoldásban felhasznált segédtételre, hogy 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 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 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 olyan szakasz végpontjait, amelyeknek ez a metszéspontja. A maradó pontokkal addig ismételhetjük az eljárást, amíg legalább pont marad, tehát ponttal még -szer, általában ponttal -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 csúcsán át legalább szakasz menne át, akkor vegyük ezeknek egy-egy, a konvex burkon kívül eső végpontját. Ezek és 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 pontja által meghatározott szakaszoknak. Valóban, vagy nem is szerepel a kiválasztott 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 -n nem mehet át szakasz.
Megjegyzések. 1. Nem nehéz látni, hogy 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 metszéspont létrehozására nem elegendő-e -nél kevesebb pont is, ill. hogy nem lehet-e bármilyen pontból kiindulva -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 pont még nem föltétlenül teszi lehetővé 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 pont esetén biztosítják 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 pont közül is mindig kiválaszthatók különböző metszéspontot szolgáltató, közös végpont nélküli szakaszok végpontjai. Ebből következik, hogy metszéspont létrehozására már pont is elegendő és általában metszéspont létrehozására pont. Valóban, ‐ általában ‐ metszéspont létrehozására alkalmazhatjuk bármelyik megoldás eljárását, és az utolsó pont közül kiválaszthatók még további metszéspontot adó szakaszok végpontjai. Az elmondottak részleteire és további megjegyzésekre külön cikkben térek vissza. |
|