|
Feladat: |
1962. évi Kürschák matematikaverseny 2. feladata |
Korcsoport: 18- |
Nehézségi fok: nehéz |
Megoldó(k): |
Császár Zoltán , Kóta József , Máté Attila , Pósa Lajos , Sebestyén Zoltán |
Füzet: |
1963/március,
100 - 107. oldal |
PDF | MathML |
Témakör(ök): |
Egyéb sokszögek geometriája, Szabályos sokszögek geometriája, Kombinatorikus geometria síkban, Gráfelmélet, Euler-féle poliédertétel alkalmazásai, Kombinatorikai leszámolási problémák, Geometriai egyenlőtlenségek, Pont körüli forgatás, Ponthalmazok, Skatulyaelv, Egyéb szinezési problémák, Teljes indukció módszere, Kürschák József (korábban Eötvös Loránd) |
Hivatkozás(ok): | Feladatok: 1963/március: 1962. é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. I. megoldás. Egy konvex -szögben átlót választunk ki úgy, hogy közülük bármely kettőnek legyen közös pontja (1. ábra). Két csúcsot akkor mondunk szomszédosnak, ha kiválasztott átló köti össze őket. Egy csúcs akkor -edfokú, ha csúccsal szomszédos. Az -edfokú csúcsok számát -vel jelöljük. Ezek szerint hiszen a baloldal értéke akkor volna , ha azoknak a csúcsoknak a számát is hozzáadnók, amelyeknek nincs szomszédjuk, azaz nem indul ki belőlük kiválasztott átló.
1. ábra Ha valamely csúcs fokszáma , akkor a belőle kiinduló kiválasztott átlók közül két ,,szélső'' közrefog egyet vagy többet. Az ilyen közrefogott átló másik végpontjában nem csatlakozhat hozzá kiválasztott átló, mert annak nem lehetne közös pontja a két ,,szélső'' mindegyikével. Eszerint esetén minden -edfokú csúcs legalább elsőfokú csúccsal szomszédos. Minden elsőfokú csúcs természetesen csak legfeljebb egy magasabb fokú csúccsal lehet szomszédos. Ebből az elsőfokú csúcsok számára következik, hiszen a harmadfokú csúcsok legalább egy-egy elsőfokúval szomszédosak, a negyedfokúak legalább kettővel-kettővel, stb. A darab kiválasztott átlónak összesen vége van. Ezek a végek a csúcsoknál helyezkednek el, minden -edfokú csúcsba vég fut. Ezek szerint Ebből az egyenletből az előzők felhasználásával
következik. Bebizonyítottuk tehát, hogy valóban .
Megjegyzések. 1. Megoldásunk az átlókról csak azt használta ki, hogy azok a csúcsokat összekötő egyenes szakaszok. Változatlanul helyes marad tehát a megoldás, ha a sokszög oldalait is az átlói közé soroljuk, ha tehát azt bizonyítjuk, hogy egy konvex -szög csúcsait összekötő szakaszok közül nem lehet -nél többet úgy kiválasztani, hogy bármely kettőnek legyen közös pontja. 2. Csak ott gondoltunk arra, hogy egy konvex sokszög csúcsairól van szó, ahol a ,,közrefogott'' átlókról mondhattuk, hogy elsőfokú csúcsokba vezetnek. Itt sincs azonban erre szükség. Ha egy pontból más-más irányba három szakasz indul, akkor sohasem csatlakozhat mindegyikhez annak végpontjában olyan szakasz, amelynek a pontból kiinduló másik két szakasz mindegyikével van közös pontja. Ha ugyanis a három szakasz egy a ponton áthaladó egyenes által határolt félsíkban van, akkor nem mondtunk újat; ha viszont nem ez a helyzet, akkor a három szakasz egyikéhez sem csatlakozhat annak végpontjában olyan szakasz, amelynek van közös pontja a másik kettő mindegyikével. Ezek szerint azt is bebizonyítottuk, hogy ha a sík pontja közül egy egyenesen sincs kettőnél több, akkor e pontokat összekötő szakaszok közül nem lehet -nél többet úgy kiválasztani, hogy bármely kettőnek legyen közös pontja. Szükség volt itt arra a megszorításra, hogy kettőnél több pont nincs egy egyenesen. Nemcsak azért, hogy bizonyításunk, amely más-más irányba induló szakaszokról szólt, alkalmazható legyen, hanem azért is, mert pl. egy egyenesen egymást követően felvett , , , pontok , , , , összekötő szakaszai már ellentmondanának a megszorítás nélkül kimondott állításnak. 3. Megemlítjük végül, hogy a most említett általánosítások ugyanúgy kiolvashatók a következő megoldásból is.
II. megoldás. Bebizonyítjuk, hogy ‐ miként megjegyzésünkben már említettük ‐ ha nemcsak az átlókból válogathatunk, hanem az oldalakból is, akkor sem választható ki -nél több, páronként közös ponttal rendelkező szakasz. Ha az -szög csúcsai között van elsőfokú, tehát olyan, amelyből csak egy kiválasztott szakasz indul ki, akkor hagyjunk el ábránkból egy ilyen szakaszt. Eredetileg szakasz szerepelt, és együttesen végpontjuk volt. Az elhagyás után csak szakasz maradt, és végpontjaik száma is legalább -gyel kisebb: . Ha lehetséges, hagyjunk el ismét ugyanúgy egy szakaszt. Ezáltal szakaszhoz jutunk, amelyek végpontszáma . Folytassuk ezt, amíg csak lehetséges. Végül szakaszhoz jutunk, amelyeknek együttesen végpontjuk van. Az így kapott ábrában már nincs elsőfokú szögpont, de nincs -nél nagyobb fokszámú sem, mert ha egy csúcsból három szakasz is kiindul, akkor a ,,közrefogott'' szakaszok végpontja csak elsőfokú lehet, amint ezt az előző megoldásban is felhasználtuk. A végábrában ezek szerint minden végpont másodfokú. A szereplő szakasz vége tehát párosával esik egybe, azaz pontba fut. Az eredmény akkor is helyes, ha az elhagyogatások befejezése után egyetlen szakasz sem marad meg, mert akkor és . A eredményből az előzők szerint , azaz következik, ami a feladat állítása volt.
III. megoldás. Közömbös, hogy melyik konvex -szög átlói közül akarunk megfelelő módon lehető legtöbbet kiválasztani, hiszen két átló közös pontjának létezése csak azon múlik, hogy az átlók végpontjai a sokszög határán elválasztják-e egymást, illetőleg vannak e közöttük egybeesők. Elég ezért, ha a feladat állítását a szabályos -szögre bizonyítjuk be. A szabályos -szög átlóit csoportokba soroljuk, egy csoportba sorolva az egymással párhuzamosakat. Ha belátjuk, hogy nincs -nél több csoport, bebizonyítottuk a feladat állítását, hiszen akkor -nél több átló kiválasztásakor arra kényszerülünk, hogy egy csoportból több átlót válasszunk ki, s az ilyen párhuzamos átlóknak nincs közös pontjuk. Az említett csoportok száma valóban nem lehet -nél nagyobb. Ha ugyanis a sokszög középpontjából merőlegest állítunk egy átlóra, ez a merőleges egyenes a sokszögből csak csúcsban vagy egy oldal felezőpontjában léphet ki, ti. aszerint, hogy a sokszög kerületének az átló végpontjait összekötő, a merőleges által felezett része páros vagy páratlan sok oldalból áll-e (2. ábra). Minthogy csúcs és oldalfelezőpont van, minthogy továbbá minden merőleges e pont közül más-más kettőt metsz ki, csak ilyen merőleges lehet. Mivel az egy csoportba sorolt átlók ugyanarra az egyenesre merőlegesek, a csoportok száma valóban nem lehet -nél nagyobb.
2. ábra
Megjegyzések. 1. Beláttuk, hogy a feladat előírása szerint nem választható ki -nél több átló. Kérdés, átló kiválasztható-e. Nyilván nem választható ki, ha értéke vagy , mert a háromszögnek nincs átlója, a négyszögnek pedig csak két átlója van. Ha viszont , akkor mindig kiválasztható átló az előírt módon, amint ezt a 3. ábra könnyen általánosítható példája bemutatja. Igaz marad ez természetesen akkor is, ha az oldalak kiválasztását is megengedjük. Ebben az esetben azonban nincs már szükség a háromszög és a négyszög kirekesztésére.
3. ábra Nem választható ki viszont minden esetben páronként közös ponttal rendelkező összekötő szakasz, ha nem egy konvex sokszög csúcsairól, hanem a sík pontjáról van szó. Ha az egyik pontot az összes többivel összekötjük, az előírást kielégítő szakaszt kapunk. Többet nem kaphatunk pl. akkor, ha az csúcsairól és a háromszögben haladó körív további pontjáról van szó (4. ábra). Ezt a következőképpen láthatjuk be:
4. ábra -ból csak szakasz indul ki. A ív pontját összekötő szakaszok közül is csak választható ki az előírásnak megfelelően, hiszen ezek egy konvex -szög csúcsai. Ha -ból induló szakaszt is és a ív pontjait összekötő szakaszt is kiválasztunk, akkor ezek közös pontja csak az -ból induló szakasz másik végpontja lehet. Ha tehát a kiválasztott szakaszok között csak egyetlen -ból induló van, akkor ennek másik végpontja szükségképpen minden más kiválasztott szakasznak is végpontja, s ezért így is csak szakaszhoz juthatunk. Ha viszont két -ból induló szakaszt és a ív egy húrját is kiválasztjuk, akkor ezek szükségképpen háromszöget alkotnak, és további szakasz már nem választható hozzájuk az előírás megsértése nélkül. Megemlítjük itt még, hogy ha tetszőleges -szög esetében csak a belső átlók közül válogathatunk, akkor még páronként közös ponttal rendelkező sem választható ki minden esetben, hanem csak . Az 5. ábra példája mutatja, hogy többet nem követelhetünk meg. Nem nehéz bebizonyítani, hogy ha , akkor két csatlakozó belső átló mindig található, e bizonyítást azonban az olvasóra hagyjuk.
5. ábra 2. Felmerül a kérdés, hogy ha a sík (hármasával nem egy egyenesen elhelyezkedő) pontját összekötő szakaszok közül ki lehet választani páronként közös ponttal rendelkezőt, akkor ez az szakasz milyen ábrát alkothat. Bebizonyítjuk, hogy csak egy páratlan oldalú csillagsokszög adódhat, amelyhez még a csúcsaiból induló, az odafutó oldalak szögtartományában haladó szakaszok járulhatnak (6. ábra).
6. ábra Második megoldásunk mutatja, hogy az elsőfokú pontokba futó szakaszok elhagyása után csupa másodfokú ponttal rendelkező ábrához kell jutnunk (ehhez az eredményhez I. megoldásunk alapján is eljuthatunk). Ez az ábra most nem lehet üres, mert akkor az utolsó elhagyás egyszerre két végpontot szüntetne meg, s így csak az egyenlőtlenség lehetne érvényes, ami kizárja teljesülését. Eszerint az elhagyások után maradó ábrában zárt töröttvonal található, mert valamelyik szakaszon elindulva a pontok másodfokúsága miatt mindig folytathatjuk utunkat csatlakozó szakaszon, és így valamikor már bejárt szakaszhoz kell érnünk. Minthogy az ilyen zárt töröttvonal szakaszai vagy csatlakoznak, vagy metszik egymást, csillagsokszöghöz jutottunk. Ennek szükségképpen páratlan sok csúcsa van. Ha ugyanis egy szakasza, akkor a további csúcsok a szakaszok metszése miatt váltakozva az egyenes egyik és másik oldalán helyezkednek el, de közülük az -val és -vel szomszédos ugyanazon az oldalon van, hiszen az ezeket -vel összekötő szakaszok is metszik egymást. Megvizsgáljuk, hogy a már megtalált csillagsokszögön kívül milyen szakaszok szerepelhetnek még az eredeti ábrában. Ha egy pont a csillagsokszög csatlakozó , oldalai által meghatározott szögtartományban vagy csúcsszögének tartományában van, akkor belőle csak -be futhat szakasz, mert különben nem volna közös pontja és mindegyikével. Ilyen szakasz is csak akkor felelhet meg, ha magában az szögtartományban van, mert különben nem volna közös pontja a csillagsokszög további oldalaival, amelyek ezen a szögtartományon belül kötik össze az , szakaszokat. Állításunk teljes bizonyításához elég már csak azt igazolnunk, hogy a sík minden pontja a csillagsokszög valamelyik szögének vagy szöge csúcsszögének tartományában helyezkedik el. Ennek igazolására az egyenest körül elforgatjuk úgy, hogy az szögnek és csúcsszögének tartományát végigsöpörve helyzetbe jusson. Ezt követően körül forgatjuk el ugyanúgy, majd a következő csúcs körül, míg végül is eredeti helyzetébe tér vissza, tehát együttesen egész számú többszörösével fordul el. Nem lehetséges azonban, hogy az egyenes -nál többet forduljon el. Az ellenkező esetben ugyanis egyenesünk az első félfordulat során olyan helyzetet is elfoglal, amelyen a csillagsokszög egyetlen csúcsa helyezkedik csak el, ti. az, amely körül éppen forgatunk. A második félfordulat során egyenesünk -val párhuzamos helyzetbe jut. Azonos helyzetről nem lehet szó, mert nem tartalmaz második csúcsot. A párhuzamos , egyenesek mindegyike kettévágja a csillagsokszög egy-egy szögét, ezért e szögek egy-egy szára a párhuzamosok sávján kívül helyezkedik el. Így tehát az ezeket a szárakat szolgáltató sokszögoldalaknak a feltételezett esetben nem lehetne közös pontjuk. Már csak azt kell belátnunk, hogy ha egy egyenes a síkban mozog, és -os elfordulás után eredeti helyzetébe tér vissza, akkor mozgása során a sík minden pontján áthalad. Ez valóban így van, mert ha valamely pontnak nem volna meg ez a tulajdonsága, akkor -ből mindig félegyenest indíthatunk, amely a mozgó egyenest merőlegesen metszi. Ez a félegyenes körül forog, és a -os elfordulás után ellentétes irányú lesz. Nem metszheti ezért merőlegesen ugyanazt az egyenest, amelyet a mozgás kezdetekor metszett. 3. Felvetjük azt a kérdést is, hogy hányat kell kiválasztani egy konvex -szög átlói közül, hogy bizonyosan legyen ezek között olyan, amelyeknek páronként nincs közös pontja. Feladatunk a esettel foglalkozott. Ebben az esetben átló kiválasztása megfelel, de kevesebb nem. Könnyű belátni, hogy a felvetett általános esetben átló kiválasztása megfelel, sőt megfelel akkor is, ha nemcsak az átlók, hanem az oldalak közül is válogathatunk. Ez harmadik megoldásunkból szinte közvetlenül kiolvasható, mert ha átlót vagy oldalt választunk ki az csoportból, akkor valamelyikből legalább -et kell kiválasztanunk. Nehezebb megmutatni, hogy kisebb szám nem felel meg. Megmutatjuk, hogy ez valóban így van, vagyis olyan előírást adunk a konvex -szög átlói közül átló meghúzására, hogy ne lehessen ezek közül páronként közös pont nélküli átlót kiválasztani. Csak akkor van értelme ilyen előírás megadásának, ha az -szögnek egyáltalában van páronként közös pont nélküli átlója. Ez csak akkor igaz, ha . Ha ugyanis olyan átlókat tekintünk, amelyeknek nincs közös pontjuk, akkor bármelyiknek bármelyik oldalán vagy található olyan csúcs, amely nem végpontja átlóink egyikének sem, vagy pedig van ezen az oldalon további átló. Ez utóbbi esetben tovább haladhatunk, és esetleg újabb meg újabb átlóhoz jutunk, de végül is el kell jutnunk olyan csúcshoz, amely átlóinknak nem végpontja. Ilyen csúcs ezek szerint legalább kettő van, ti. egy átló mindkét oldalán legalább egy. Ha tehát átlóról van szó, akkor ezek végpontján kívül még legalább két csúcsnak kell lennie. Legyen tehát , és legyenek az -szög csúcsai sorban | | Rajzoljuk meg ebben a konvex -szögben mindazokat az átlókat, amelyeknek legalább az egyik végpontja jelű, továbbá kivételével mindazokat az átlókat, amelyek két jelű csúcsot kötnek össze (7. ábra; a 3. ábra a esetben ugyanezt mutatja be). Könnyű ellenőrizni, hogy összesen átlót rajzoltunk meg.
7. ábra Állítjuk, hogy ezek közül az átlók közül csak darab páronként közös pont nélküli választható ki. Ezt -ra vonatkozó teljes indukcióval bizonyítjuk be. Már tudjuk, hogy állításunk a esetben helyes. Legyen tehát , és tegyük fel, hogy állításunk minden olyan esetben helyes, amikor szerepét -nál kisebb szám tölti be. Ha valamennyi kiválasztott átlónak van jelű csúcsa is, akkor számuk nem lehet -nál nagyobb, hiszen csak darab jelű csúcs van. Elég ezért azzal az esettel foglalkoznunk, amikor olyan átlót is kiválasztunk, amely két jelű csúcsot köt össze. Megvizsgáljuk, hogy két oldalán hány további átló választható ki. Vágjuk fel tehát -szögünket két sokszögre, -re és -re. csúcsai csak és jelűek, csúcsai között pedig a jelűek is szerepelnek. Helyezkedjék el a jelű csúcsok közül darab határán, pedig határán. Nyilván , viszont is lehetséges. Azt állítjuk, hogy -ben csak olyan átló választható ki, amelyeknek egymással és -val nincs közös pontjuk. Már beláttuk, hogy darab páronként közös pont nélküli átló csak legalább oldalú sokszögben van. legfeljebb éppen ennyi oldalú lehet (ha ti. vagy is szerepel végpontjai között), azonban olyan átlók számát vizsgáljuk, amelyeknek -val sincs közös pontjuk. Az ilyen átlók pedig annak az sokszögnek is átlói, amelyet -ből kapunk, ha egy átlójával a oldalt és egy szomszédos oldalát levágjuk (8. ábra). Minthogy legfeljebb oldalú, -ből sem lehet az előírt módon átlónál többet kiválasztani. -ben csak akkor van egyáltalában átló a megrajzoltak közül, ha , azaz van -nek jelű csúcsa is. Feltesszük tehát, hogy . Vizsgáljuk meg, hogy határán a csúcsok betűjelzése olyan elrendezésű-e, mint -szögünkben, természetesen helyett csak darab jelű csúccsal. Ez bekövetkezik, ha végpontjai között vagy is szerepel. Minden más esetben ugyancsak elérhetjük ezt azáltal, hogy -bő1 egy átlóval a oldalt és egy csatlakozó, jelű pontba vezető oldalt levágunk (8. ábra). A kiválasztható átlók számát vizsgálva az így kapott sokszögre térhetünk át, hiszen csak olyan átló választható ki, amelynek -val sincs közös pontja. Minden esetben alkalmazhatjuk tehát az indukciós feltevést, s ezért kimondhatjuk, hogy -ből a követelményt kielégítő módon nem lehet átlónál többet kiválasztani.
8. ábra Ezek szerint az általunk megrajzolt átló közül kiválasztható, páronként közös pont nélküli átlók száma (magára -ra is gondolva) valóban legfeljebb . Megoldatlan kérdés, hogy ha a most tárgyalt problémát nem egy konvex -szögre, hanem a sík pontjára vetjük fel, vajon szintén adja-e a feleletet. 4. Feladatunk problémájának utolsó általánosításaként még az angol Conway sejtését említjük meg. E sejtés szerint, ha a sík pontját összekötő vonalakat rajzolunk, amelyek közül bármely kettőnek vagy van közös végpontja, vagy pedig egyetlen pontban metszik egymást, de más közös pontjuk nincs, akkor ezeknek az összekötő vonalaknak a száma csak legfeljebb lehet. Hangsúlyozzuk, hogy vonalak érintkezési pontja nem metszéspont, a vonalak érintkezését kizártuk. Eldöntetlen kérdés, hogy vajon ez a sejtés helyes-e. Említést érdemel, hogy a vizsgált ábrák itt lényegesen mások, mint az összekötő szakaszokra felvetett problémánál, és nem csak a vonalak görbülése miatt. Ezt a 9. ábra is mutatja, melyben pontot vonal köt össze az előírásnak megfelelően, mégpedig ciklikus módon. Láttuk, hogy szakaszok esetében ez csak páratlan sok pontra lehetséges.
9. ábra Olvasóink is megkísérelhetik a vonalakra vonatkozó probléma megoldását. Ha valakinek sikerül az előírásnak megfelelően úgy rajzolnia vonalakat, hogy számuk nagyobb, mint végpontjaik együttes száma, akkor megoldotta a problémát. Nehezebb a probléma lezárása, ha nemcsak nem sikerül ilyen ábrát rajzolni, hanem ilyen ábra nincs is. Ebben az esetben ennek bebizonyítására volna szükség. |
|