Feladat: 1480. matematika gyakorlat Korcsoport: 16-17 Nehézségi fok: -
Füzet: 1974/március, 113 - 114. oldal  PDF  |  MathML 
Témakör(ök): Hamilton-út, -kör, Kombinatorikus geometria síkban, Kombinatorikai leszámolási problémák, Maradékos osztás, Gyakorlat
Hivatkozás(ok):Feladatok: 1973/szeptember: 1480. 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.

Írjuk fel az 1‐9-ig terjedő számoknak azokat a szomszédjait, amelyek a kívánt feltételt kielégítik. Az 1-nek nem lehet szomszédja az őt 3-ra, 6-ra, 9-re kiegészítő szám, vagyis 2, 5 és 8, hasonlóan az 5-re és a 10-re, valamint 7-re kiegészítő 4, 9 és 6, tehát

 


1 szomszédja lehet M    3,  7,
 

Hasonlóan adódik, hogy
 

2  szomszédja lehet  M6,9,3  szomszédja lehet  1,5,8,4  szomszédja lehet  7,9,5  szomszédja lehet  3,6,8,6  szomszédja lehet  2,5,7,7  szomszédja lehet  1,4,6,9,8  szomszédja lehet  3,5,9,9  szomszédja lehet  2,4,7,8.  
 

Láthatjuk, hogy 1-nek, 2-nek és 4-nek szomszédjaként csak két-két szám írható be, ez a két szomszéd közrefogja a számot s a három szám egymás után szerepelhet csak. Kezdjük a felírást az egyik ilyen számmal, pl. az 1-gyel. Két közrefogó szomszédja 3 és 7. A 7 a 4-nek is közrefogó szomszédja, tehát 7 után feltétlenül 4, majd 9 következik, ami után hasonlóan 2-t, majd 6-ot kell írnunk: 3, 1, 7, 4, 9, 2, 6. Ezzel már hét számot elhelyeztünk, és a két szomszéddal bíró számok bármelyikével kezdjük is a felírást, e hét szám sorrendje egyértelműen meg van határozva.
A hátramaradó 5 és 8 elhelyezésére is csak egy lehetőségünk marad, mert egyrészt a 8-nak a megengedett szomszédai között nem szerepel a sorunk végén álló 6-os, másrészt viszont az 5-ös beállítható a 6-os és 8-as közé
Feladatunk tehát megoldható. (Lényegében csak egyetlen megoldás létezik. Ugyanis az elsőként kitöltendő helyre írt szám és a körüljárás iránya itt nem lényegesek.)
 

 

Megjegyzés. Ábránkon rajzi segítséggel kerestünk megfelelő sorrendet. Először vékony vonallal összekötöttük az 1,2,...,9 számok párjai közül azokat, amelyek alkalmasak szomszédoknak. A fenti táblázat 26 megengedett szomszédsága így fele annyi, 13 összekötést adott. Majd a csupán két összekötést mutató számok környezetében vastagítással és ívvel mintegy "véglegesítettük'' a ‐ követelés szerint 9 szomszédságból kialakulandó ‐ körüljárás két-két szomszédságát. Ez hat összekötést rögzített le, egyszersmind felhasználhatatlanná tett egyes további vékony vonalakat: a 7-esből kiindulva kettőt, a 9-esből további egyet, a 3-asból egyet, ezeket mindkét végpontjuknál áthúztuk. Ezek után az 5-ösnek és a 8-asnak is csak két-két használható szomszédsága maradt, kialakult egy lehetséges útvonala a számok egymás után írásának, amely önmagában záródik.