|
Feladat: |
1408. matematika feladat |
Korcsoport: 16-17 |
Nehézségi fok: nehéz |
Megoldó(k): |
Babai László , Bárány Imre , Csernátony Cs. , Domokos László , Eff Lajos , Egri R. , Faragó T. , Gáspár András , Havas János , Herényi István , Kiss Árpád , Klocknicer Imre , Köves M. , Lévai F. , Losonci Z. , Recski A. , Szeidl L. , Szeredi Péter , Vincze András |
Füzet: |
1967/november,
101 - 103. oldal |
PDF | MathML |
Témakör(ök): |
Gráfelmélet, Kombinatorikai leszámolási problémák, Teljes indukció módszere, Feladat |
Hivatkozás(ok): | Feladatok: 1965/szeptember: 1408. matematika feladat |
|
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. Jelöljük a metszéspontokat -mel, az egyeneseket -nel úgy, hogy rendje legyen és -n darab pont legyen. Vegyük észre, hogy c)-ből és f)-ből következik, hogy és fordítva is, c)-ből és g)-ből következik f). Ugyancsak következik c)-ből, d)-ből és g)-ből e), így elég az a) ‐ d) és g) állításokat igazolni. I. Egy egyenesen végighaladva számoljuk össze kétféleképpen, hány egyenest lépünk át. Egyrészt átlépjük a többi egyenesek mindegyikét egyszer, tehát egyenest, másrészt az egyes egyeneseken minden pontban egyenest lépünk át. Eszerint az egy egyenesen levő pontokra az értékek összege . a) Megállapításunkból következik, hogy az egy egyenesen levő -kre az -ek közt a páratlanok ‐ vagyis az egyenesen levő páros rendű pontok száma ‐ páros, ha páros, vagyis ha páratlan, és a mondott szám páratlan, ha páros. b) A fenti megszámlálást minden egyenesen elvégezve egyrészt átlépést számlálunk, ez áll b) jobb oldalán; másrészt minden ponton -szer haladunk át és minden alkalommal átlépést, tehát összesen átlépést számolunk össze, tehát pontok szerint számolva össze b) bal oldalát kapjuk. Ezzel az összefüggést igazoltuk. c) Most számoljuk össze az egyes egyenesek mentén levő pontokat. Minden egyenesen végigmenve éppen c) bal oldalát kapjuk. Másrészt egy pontot minden rajta átmenő egyenesen számba vettünk egyszer, összesen tehát -szer számoltuk. Így pontok szerint csoportosítva a jobb oldalt kapjuk. Ezzel ezt az egyenlőséget is igazoltuk. Idáig nem használtuk fel azt a feltevést, hogy nem halad át egy közös ponton minden egyenes, az a) ‐ c) állítás tehát erre az esetre is érvényes (csak triviális). d) és g) igazolásához szükségünk van arra a segédtételre, hogy ha az egyenesek nem egy ponton mennek keresztül, akkor van olyan metszéspont, mondjuk , amire . Ebből a két állítás az alábbiak szerint következik. d) Legyen a -en átmenő egyenes és . Megszámolva -en és -n az egyenes-átlépések számát és hozzászámolva még a metszéspontok számát is kivételével, egyrészt -et kapunk, ami az összefüggés jobb oldala. Másrészt -et -szer vettük számításba (mind -en, mind -n egy átlépés történt -ben), az -en és -n levő -k mindegyikében átlépést számoltunk és egyszer a pontot számba vettük, így ezek a pontok -vel járultak az összeghez; egy sem -en, sem -n nem levő pont pedig, ha van ilyen, -szer van számba véve, vagyis kevesebbszer, mint a rendje. Ezzel az egyenlőtlenséget igazoltuk. Azt is látjuk, hogy d)-ben akkor és csak akkor áll fenn egyenlőség, ha nincs metszéspont a fenti , egyenespáron kívül. Könnyű belátni, hogy ez csak úgy lehetséges, ha egyikükön ‐ mondjuk -n ‐ csak egy a -től különböző metszéspont van, ezen minden egyenes átmegy, kivéve -et, továbbá azt is, hogy ekkor . g) Teljes indukcióval bizonyítjuk az állítást. 3 egyenes esetén . Tegyük fel, hogy egyenesre igaz az állítás és vegyünk a feltételeknek megfelelő egyenest, ezeknek egy másodrendű metszéspontját, melyen átmegy az egyenes. Elhagyva -et, megszűnik metszéspont lenni és minden további, az -en levő másodrendű metszéspont is, ha van ilyen. Így a megmaradó egyenesek metszéspontjainak száma legfeljebb . Ha a megmaradó egyenesek egy ponton mennek keresztül, akkor nyilván -gyel elmetszve őket összesen metszéspont lesz. Ha nem mennek mind át egy ponton, akkor érvényes rájuk az állítás, vagyis Így g) igaz akárhány egyenesre. II. Bebizonyítjuk a d) és g) igazolásában felhasznált segédtételt, vagyis hogy feltevéseink mellett van olyan metszéspont, melynek rendje 2, más szóval amely az adott egyenes közül pontosan kettőn van rajta. Tekintsük mindegyik távolságát mindegyik olyan -től, mely nincs rajta. Legyen e távolságok legkisebbike ‐ az indexeket alkalmasan választva ‐ távolsága -től. Ekkor -en két megy át.
Legyen ugyanis a -ből -ra bocsátott merőleges talppontja. Ha -en három menne át, akkor valamelyik oldalán legalább két ilyen egyenes metszené -at, legyenek ezek és úgy, hogy a és egyenes közti hegyesszög-tartományban halad; esetleg egybeesik -vel. Ekkor távolsága és metszéspontjától kisebb lenne, mint , hiszen nem lehetne nagyobb, mint az , és egyenesekkel meghatározott derékszögű háromszögnek az átfogóra merőleges magassága, viszont nagyobb ennél. Ezek szerint -en valóban nem mehet át 2-nél több . Megjegyzések. 1. Fent csak g)-t bizonyítottuk teljes indukcióval. Ugyanígy bizonyíthatók az előző állítások is. Érdekes, hogy d) teljes indukciós bizonyítása nem használja fel a fenti mélyebb segédtételt. 2. Meg lehet mutatni, hogy csak a mondott speciális alakzatra teljesül. g) helyett a következő élesebb állítás is bizonyítható teljes indukcióval: , kivéve ha elhagyható egy egyenes úgy, hogy a többi egy ponton menjen keresztül, ekkor . Ha , akkor csak a kivételes eset állhat elő, bármelyik egyenes lehet az elhagyandó. A kivételes esetben nyilvánvalóan . Legyen most , -re legyen igaz az állítás, legyen egyenesünk, amely megfelel a feltételeknek és nem a kivételes esetet mutatja. A segédtétel szerint van olyan egyenes, amelyen van másodrendű pont. Ha elhagyása után sem a kivételes eset áll elő, akkor , s így . Ha a kivételes eset jön létre, akkor nem mehet át olyan metszésponton, amin rajta kívül egyenes megy át, de ekkor legalább 2 egyenest metsz olyan pontban, amin harmadik egyenes nem megy át, s így , tehát . Az élesebb állítás is igaz tehát akárhány egyenesre. A segédtétel rokon Gallai Tibor következő tételével: ,,legyen adva a síkban pont, melyek nincsenek mind egy egyenesen, ekkor van olyan egyenes, mely ezen pont közül pontosan kettőn megy át'' ‐ és ebből a tételből segédtételünk az ,,egyenes'' és ,,pont'', továbbá ,,metszés'' és ,,összekötés'' szó-párok egymással való kicserélése (és a szükségessé váló stiláris módosítások) útján keletkezik. Két ilyen tételt egymás duálisának mondunk. |
|