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. Megadunk egy előírást a bejárásra, mégpedig olyant, amelynél minden útszakaszon (oldalon vagy átlón) megszakítás nélkül haladunk végig, irányt csak a sokszög csúcsaiban változtatunk. Jelöljük a sokszög csúcsait (tetszés szerinti sorrendben) a , , számokkal. A -ból indulunk el, az -en, -n át visszatérünk oda, majd minden lépésben újabb csúcsot az előbbiekkel és egymással összekötő útszakaszokat járjuk be. Ha a közti útszakaszokat már bejártuk és visszatértünk -ba, akkor a következő úton megyünk tovább: | | Ezzel programunkat megvalósítottuk és visszaértünk a -ba, az eljárást tovább folytathatjuk, míg minden útszakaszt be nem jártunk.
1. ábra Az 1. ábra a szabályos -szög ilyen bejárását mutatja be. Megjegyezzük, hogy a sokszög szabályos voltát nem használtuk fel, legfeljebb, amennyiben csak egyenes útszakaszokat engedünk meg, csak annyit, hogy pont van adva, amelyek közül nincs egy egyenesen.
Langer Tamás (Budapest, Apáczai Csere J. gyak. g. IV. o. t.)
II. megoldás. A bejárás lehetőségét konkrét bejárási előírás megadása nélkül fogjuk belátni. Egy csúcsból tetszés szerint elindulva haladjunk tovább minden csúcsból valamilyen útszakaszon, amíg olyan csúcsba nem érünk, amelyikből induló minden útszakaszon jártunk már; röviden: amíg megakadunk. Ez csak az csúcsban lehet. Ugyanis minden más csúcson mindig át tudunk haladni, mert egy áthaladás ott végződő útszakaszt használ fel, így a csúcsban az egymás utáni áthaladások után bejáratlanul maradt útszakaszok száma a páros számok , sorozatán át csökken. -ban viszont a páratlan számok sorozatán át csökken ez a szám, mert az elindulás után útszakaszt hagytunk vissza. Amennyiben az -beli megakadásig nem jártuk be az egész úthálózatot, akkor javítjuk útvonalunkat úgy, hogy több útszakaszon haladjon át. Mindenesetre minden csúcson legalább egyszer áthaladtunk, hiszen bejártuk az -ból odavezető utat. Minden olyan csúcsban, ahová még fut be bejáratlan útszakasz, páros az ilyenek száma. Egy ilyen csúcsból indulva és a maradék hálózaton megtett utunkat egy más színnel rajzolva csak -ben akadhatunk meg ismét. Mármost a két különböző színű útvonalat eggyé tehetjük úgy, hogy az első bejárás során -be érkezve beiktatjuk az új színnel bejárt útvonalat, s csak ezután haladunk tovább az első útvonalon. Ha még mindig nem jártuk be az egész hálózatot, akkor ismét olyan részhálózat maradt vissza, mint az első megakadás után, s így megismételhetjük eljárásunkat. Az eredeti sokszög oldalainak és átlóinak száma véges, ezért véges számú hasonló útvonal-módosítás után egyetlen, az egész hálózatot bejáró útvonalat kapunk.
Megjegyzések 1. Feladatunk állítása egy gráfelméleti tételből is következik. 2. Megadjuk egy más, érdekes, rendszeres bejárás utasítását. A sokszög egymás utáni csúcsait ismét a számokkal jelöljük. Előkészítésül az átlókat osztályokba soroljuk, -edosztályúnak nevezzük azokat, amelyekkel a sokszöget kettévágva a kisebbik rész oldalt tartalmaz a kerületből. Így a legnagyobb osztályszám ; az oldalakat első osztályú átlóknak tekintjük, ekkor az osztályok száma . Továbbá minden átlón előre megállapítjuk a menetirányt: úgy haladunk, hogy a sokszög nagyobbik része ‐ más szóval a sokszög középpontja ‐ jobb kezünk felé essék (röviden: az átlókat irányítjuk). Így minden útszakasznak kijelöltük a kezdő és végpontját, minden csúcsban átló kezdődik (indul), és átló végződik (érkezik), minden egyes átló-osztályból egy-egy. A bejárást a következő előírások szerint végezzük: 1. A -jelű csúcsból indulunk ki. 2. Ekkor és minden ide való visszaérkezés után a még rendelkezésre álló átlók közül a legmagasabb osztályú átlón haladunk tovább. 3. A -tól különböző csúcsba érkezve ugyanolyan osztályú átlón haladunk tovább, mint amilyenen oda érkeztünk. 4. A szakasz bejárása után a csúcs megkülönböztetett szerepét átadjuk az csúcsnak, majd hasonlóan a -nek és í. t. Eljárásunk szemléletesen a következőt jelenti. -ból a átlón megindulva végigjárjuk az csúcsokat ‐ ahol a -nél nagyobb számokat a -gyel való osztásuk maradékával kell helyettesíteni ‐, míg vissza nem érünk a -ba. Ha -nek és -nek nincs -nél nagyobb közös osztója, akkor ez az összes -edosztályú átló alkotta csillag--szög bejárása után következik be .
2. ábra A esetben (2. ábra) és esete is ilyen, s így -ból indulva az összes -ad-, majd -odosztályú átlót bejárjuk, majd végigmegyünk az oldalakon. Hasonló a helyzet, ha prímszám. -szögben , és esete ilyen (lásd a csúcsok bejárás szerinti sorrendjének alábbi felsorolását). Az eset mindig ilyen, mert és relatív prímek. Ha és legnagyobb közös osztója , akkor lépés után jutunk vissza a -ba egy (egyszerű vagy csillag-) szabályos -szög bejárása után . Ekkor a többi -ed osztályú átló további, az elsővel egybevágó sokszöget ad. Ezeket akkor járjuk be, amikor az csúcs veszi át a szerepét. A szabályos -szög elveink szerinti bejárásában esetére csillagötszög, esetére közönséges ötszög adódik a , , csúcsokból kiindulva, esetére pedig hasonlóan szabályos háromszög a , , , , csúcsokból kiindulva. A csúcsok alábbi felsorolásában egy-egy ilyen vonalrész bejárásának befejezését, valamint a -szög 1‐1 oldalán való áthaladást is, pontosvessző jelzi. Ezzel lényegében be is bizonyítottuk, hogy a bejárási előírás 3. pontja mindig teljesíthető. Minden útszakaszon áthaladtunk ‐ ahol ( esetén itt is a mondott helyettesítéssel) ‐, és csak egyszer. Ha ugyanis nem haladtunk át rajta, mielőtt átveszi a szerepét, akkor a szerepátvétel után sorra vesszük a -ből kiinduló összes még be nem járt átlót, utoljára pedig a oldalt, és ezzel adjuk át a pont szerepét a -nek. ‐ Hátra volna azonban még a (*) és (**) jelű állítások bizonyítása.
Szűcs András (Budapest, Fazekas M. gyak. g. III. o. t.) dolgozata alapján, kiegészítésekkel
3. Ha prímszám, akkor a következő előírás is a fenti útvonalra vezet: 1. A átlón indulunk és 2. minden csúcsból az onnan kiinduló legmagasabb osztályú átlón haladunk tovább. ‐ Ha azonban összetett szám, akkor így a fenti oldalú csillagsokszögeket nem mindig egyfolytában járjuk be. Meg lehet mutatni, hogy ekkor viszont a pontba mindig ugyanolyan osztályú átlón érkezünk, amilyenen onnan utoljára elindultunk. | | Lásd pl. Ruzsa I.‐Cser A.‐Könyves Tóth K.‐dr. Hajnal A.‐Bakos T.: Matematika, a matematikai osztályok számára, III. kötet, 325‐400 o., élesebben 363─355. o. Tankönyvkiadó, Budapest, 1966.Lásd pl. Kürschák J.‐Hajós Gy.‐Neukomm Gy.‐Surányi J.: Matematikai versenytételek, I. rész, 3. kiad., Tankönyvkiadó, Budapest, 1965, 46. o. |