Feladat: 666. matematika gyakorlat Korcsoport: 14-15 Nehézségi fok: átlagos
Megoldó(k):  Kultsár Szabolcs ,  Padányi Piroska ,  Szidarovszky Ferenc 
Füzet: 1961/október, 73 - 74. oldal  PDF  |  MathML 
Témakör(ök): Gráfelmélet, Sakk, Gyakorlat
Hivatkozás(ok):Feladatok: 1960/december: 666. matematika gyakorlat

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) A hálózatot megrajzolva gondoljuk és (más színű ceruzával) utánarajzoljuk. A tábla osztó- és határvonalainak metszéspontjait csomóknak nevezve a belső csomókból 4, a sarkiakból 2 út vezet a szomszédos csomókba (páros csomók), a határ- és osztóvonalak csomóiból pedig 3 (páratlan csomók).
A ceruzafelemelések legkisebb számát keresve a ceruzát csak olyan V végpontban emeljük fel, ahol nem haladhatunk tovább, nyilván csak csomóban, ha ti. az odatartozó utolsó útvonalat megrajzoltuk. Kezdőpont is csak csomó lehet, mert a ceruzavonal visszafelé is meghosszabbítható. Minden K kezdőpontban 1 utat használunk el, ezért az ilyen csomó ‐ a hátralevő utak szempontjából ‐ ellentétes párosságúvá változik (páratlanból párossá, párosból páratlanná lesz). Ha pedig egy csomón áthaladunk, hátralevő útjainak száma 2-vel csökken, ezért párossága nem változik. Tehát sarki csomó összes útjainak megrajzolását egyszeri áthaladással befejeztük, a belső csomókéit pedig két áthaladással (hacsaknem ilyenből indultunk ki). Páratlan csomónak viszont egy áthaladás után csak 1 szabad útja marad, a következő ideérkezéskor a ceruzát fel kell emelnünk.
Nyilvánvaló ezekből, hogy K gyanánt csak eredetileg páratlan csomót célszerű használni, és ‐ ezt az elvet megtartva ‐ csak eredetileg páratlan csomó adódik V-nek. A K és V pontok száma egyenlő. Már most oldalanként 7 páratlan csomó van, összesen 28, ezekből 14K és 14V lesz, tehát a ceruzát 13-szor kell átemelnünk és 14-edszer befejezésül felemelnünk.

 
 
1. ábra
 

b) Előbbi útvonalunkat felemelés nélkülivé kiegészítve minden V-től a következő K-ig levő utat másodszor is meg kell rajzolnunk, ezért mindegyik V-höz lehető közeli új K-t kell választanunk. Az egy oldalon levő szomszédos páratlan pontok közti távolságok egyenlők a mezők c oldalával, két szomszédos oldal legközelebbi páratlan pontjai pedig egymástól (a vonalon) 2c-re vannak. Az egy-egy oldalon levő 7 páratlan pont három szomszédos V-K párba kapcsolható, ez a 4 oldalon 4⋅3c=12c többletutat eredményez. Ha az oldalanként fennmaradó 1‐1 páratlan pontot úgy választjuk, hogy a tábla két szemközti csúcsának szomszédai legyenek (az ábrán A, B, C, D), továbbá az összefüggő útvonal K és V-jének A-t és D-t választjuk, akkor B és C között további 2c többletútra van szükség.
A tábla kerülete 32c=128, így c=4 cm, a hálózat vonalainak hossza 2⋅9⋅8c=576 cm, a kétszer bejárt út 14c=56 cm, tehát a keresett legrövidebb út hossza 632 cm. Az 1. ábra mutatja, hogy ilyen utánarajzolási útvonal valóban létezik.
 

Kultsár Szabolcs (Hajdúböszörmény, Bocskai I. g. II. o. t.)
Padányi Piroska (Budapest, Radnóti M. g. I. o. t.)
 

Megjegyzés. Ha a hálózat 8-szor 8 mező helyett 2n×2n mezőt tartalmaz, vagyis mindkét irányban 2n+1 számú, 2nc hosszú szakaszból áll, akkor a páratlan csomók száma 4(2n-1), és így a ceruzát (a befejezéssel együtt) 2(2n-1)= =4n-2-szer kell felemelnünk. Ha ezt a hálózatot akarjuk felemelés nélkül utánarajzolni, akkor az úthossz
[2(2n+1)2n+4(n-1)+2]c=(8n2-8n-2)c.
Ha pedig (2n+1)2 mezős sakktábláról van szó, akkor a 4⋅2n páratlan csomó 4n felvevést tesz szükségessé, ill. a ceruza teljes útja
[2(2n+2)(2n+1)+4n-1]c=(8n2+16n+3)c,
ugyanis itt egy-egy oldal 2n páratlan csomójának V-K párba kapcsolása nc többlet utat igényel, az egész hálózaton azonban 1 ilyen mégis felesleges, mert 2 (szomszédos) csomó az egész út K és V-je gyanánt szerepel. 7×7-es sakktáblára ilyen útvonal létezését a 2. ábra mutatja.
 
 
2. ábra
 

(A szimmetria meghagyása végett K és V nincs kijelölve, e célra bármelyik 2-szer bejárt c-szakasz végpontjai vehetők.) A vonalvezetés bármely (1-nél nagyobb) páratlan mezőszám esetén használható, mert 2n+1-ről 2n+3-ra áttérve mindkét irányban 2-vel több párhuzamosunk van, és így az oda-vissza utak száma 1‐1-gyel növekszik. Az 1. ábra elve is bármely páros mezőszámra használható.
 

Szidarovszky Ferenc (Budapest, Fazekas M. gyak. g. II. o. t.)