Feladat: Gy.1693 Korcsoport: 14-15 Nehézségi fok: átlagos
Füzet: 1978/február, 68 - 69. oldal  PDF  |  MathML 
Témakör(ök): Kombinatorikus geometria síkban, Bolyongási feladatok, Négyzetrács geometriája, Gyakorlat
Hivatkozás(ok):Feladatok: 1977/április: Gy.1693

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.

Előre bocsátjuk a következő állításokat, melyek a feladat követelményeiből adódnak. A szimmetria miatt elegendő egy negyedtábla bejárását vizsgálni. A bejáráshoz valahol be kell lépni a negyedbe és ki is kell jönni, mert különben záródna az útvonal anélkül, hogy valamennyi szögpontot bejártuk volna. Be- és kijövetelkor utunk a tábla más-más középvonalát metszi át, nem metszheti ugyanazt, mert akkor egy fél táblán zárt útvonalat kapnánk. Minden középvonalat csak egyszer metszhetünk, mert ha kétszer metszenénk, utunk két nem összefüggő részre esne szét.

 
 
1. ábra
 

Ezután válasszuk ki további vizsgálatainkra a tábla bal felső negyedét. A bal felső sarokban levő szögpontba két él vezet, az egyiken ki-, a másikon befelé haladhatunk. Ez a két él tehát minden lehetséges útvonalunkban szerepelni fog. Vizsgáljuk meg, hogy a két élhez hányféleképpen juthatunk. Erre 3 lehetőségünk van (1. ábra). Nevezzük ezeket A, B, C típusú utaknak. Minden bejárás ezek valamelyikét kell hogy tartalmazza. Mindegyik esetben a másik irányból csatlakozhat hozzájuk egy A, B vagy C típusú út. Ez összesen 9 lehetőség: AA, AB, AC, BA, BB, BC, CA, CB, CC. A négyzet átlós szimmetriája miatt az AB és BA, BC és CB, AC és CA egymás tükörképei lesznek, és így nem adnak új megoldást.
A maradék 6 eset a 2. ábra szerinti.
 
 
2. ábra
 

Ezek közül AA, BB, CC nyilván nem felel meg a feltételeknek. AA és BB esetén úgy lépünk ki, hogy nem jártunk be minden pontot, CC esetén pedig van zárt utunk. A másik 3 esetben van a feltételeknek megfelelő útvonal és könnyen belátható, hogy csak egyféle.
Ezzel megadtuk az összes lehetséges útvonalat. A kapott útvonalakat a négyzet átlójára tükrözve még 3 megoldást kapunk, de ezeket nem tekintjük lényegesen különbözőknek.
 
 
3. ábra