Egy sakktáblát szeretnénk bejárni lóugrásban úgy, hogy minden mezőre pontosan egyszer lépjünk. Lehetséges-e ez, ha a tábla 3*5-ös?

Nem hinném.

Én úgy tudom, h a ló azért kapott helyet a táblán, mert voltak olyan mezők, amikre a futó meg a többi soha nem tudott volna lépni, ezért kellett a ló.

Nevezzük el a tábla mezőit, az első sor legyen A1, A2 ... A8, a második sor B1-B8, a harmadik meg C1-C8.

Tekintsünk egy olyan gráfot, aminek a csúcsai a mezők, és 2 csúcs akkor van összekötve, ha azok lóugrással elérhetőek (tehát pl. A2 össze van kötve C1-gyel, C3-mal, és B4-gyel).

Ahhoz, hogy minden mezőre pontosan egyszer lépjünk, egy Hamilton-utat kell megtennünk.

B1 és B8 mezők csak A3 és C3 mezőkkel lehetnek összekötve, mivel A3 és C3 közül az egyiken be kell ugrani a lóval, a másikra pedig ki kell ugrani, viszont ha B1 és B8 is össze lenne A3-mal és C3-mal, akkor egy körünk lenne a gráfban, ami nekünk nem jó, mert mi egy utat szeretnénk, ami minden csúcsot tartalmaz, tehát B1, B8, A3 és C3 közül valamelyik 2 csúcsnak kell lenni a Hamilton-utunk 2 végpontjának.

Viszont a sakktábla sarkai is csak 2 mezővel lehetnek összekötve, ezek közül az egyik a sakktábla közepe, viszont így a sakktábla közepének 4 csúccsal kell összekötve lennie, ami azt jelentené, hogy kétszer mentünk rajta keresztül, mi pedig csak egyszer tudunk, tehát a négy sarok közül kettőnek a Hamilton-utunk végpontjának kell lennie, viszont B1, B8, A3 és C3 közül is kettőnek végpontnak kell lennie, egy útnak pedig csak 2 vége van, tehát ellentmondásba ütköztünk, nincsen Hamilton-út a gráfban, a 3*5-ös sakktábla nem járható úgy be lóval, hogy minden mezőre csak egyszer lépünk.

Nevezzük el a sorokat 1,2,3-mal, az oszlopokat a,b,c,d,e-vel.

Páratlan számú mező van. Mondjuk legyen feketéből 8, fehérből 7. Ekkor ha van bejárás, azt biztos, hogy feketén kell kezdeni és egy másik feketén befejezni. A fehér mezőkbe pedig be is lépünk és ki is kell lépnünk a bejárás során.

Az a2 és e2 mezők fehérek. Mindkettőből két másik mező érhető csak el: c1 és c3. Vagyis mondjuk a2-be c1-ből jutunk el, majd c3-ba megyünk tovább. Ezzel bejártuk az a2, c1 és c3 mezőket. Akkor viszont e2 később már nem lesz elérhető, mert oda is csak c1-ből vagy c3-ból juthatnánk, de azokban a mezőkben már jártunk, amikor a2-ben voltunk. Ha pedig közvetlenül a c1, a2, c3 mezők után e2-be megyünk, akkor nem tudunk kilépni onnan, mert c1-ben és c3-ban is jártunk már. Csak úgy tudnánk a2-be és e2-be is eljutni, ha valamelyikük lenne a kiinduló vagy a befejező mező, de azoknak feketéknek kell lenniük, így ellentmondásra jutottunk.

Nem lehetséges.

Előttem levő már elmondta a dolog nyitját, mindenesetre közben én is összetákoltam a magam (talán áttekinthetőbb) válaszát.

Az érthetőség kedvéért illusztráltam is a megoldást:

[link]

A lényeg, hogy ha a sakktáblát felírjuk egy gráfként, aminek a tábla mezői a csúcsai, és a csúcsok közötti kapcsolatot az jelenti, hogy lóugrással átléphetünk-e az egyikből a másikba, egy olyan gráfot kapunk, aminek 8 db 2-fokú, 4 db 3-fokú, és 3 db 4-fokú csúcsa lesz. Azaz összesen 8 kettő-, és 7 ettől nagyobb fokú. Továbbá megfigyelhető, hogy a 2-fokú csúcsok kizárólag 3, vagy 4-fokú csúccsal vannak összekötve. Ebből a két információból adódik, hogy a bejárás akkor és csak akkor lehetséges, ha 2-fokú csúcsból indulunk, valamint 2-fokúból 3/4 fokúba, onnan pedig ismét 2-fokúba lépünk tovább.

Viszont elérkezünk egy problémához.

A képen is látszik, hogy van két olyan 2-fokú csúcsunk, ami ugyanazzal a két 4-fokúval van összekötve, amik ezeken kívül csak 2-2 3 fokú csúccsal vannak összekötve. Ha a fent említett sorrend szerint akarunk haladni (márpedig tisztáztuk, hogy csak úgy haladhatunk), akkor a 4-es csúcsokból nem léphetünk 3-asba, így "csapdába" kerülünk, és a bejárás elakad.

Ebből következik, hogy a gráfnak nincs Hamilton-útja, azaz a sakktábla nem járható be.

Egy sokadik megoldás :) Rajzoljuk fel a gráfot, és a 2 fokszámú csúcs éleit emeljük ki, mivel azokon kötelezően át kell haladnunk (más irány nincs). Látható, hogy a középső mezőből így 4 élt emeltünk ki, ami azt jelenti, hogy 2-szer kellene rálépni és kétszer kilépni. Ami nem lehet, mert egy mezőre 1-nél többször nem léphetünk. Viszont ha ezek közül nem is kell használni mindet, de 3-at biztosan, de még úgy sem lehet megoldani.

Egyébként, ha jól sejtem, akkor ez véges/diszkrét matekra kell (ráadásul csillagos feladat), ahol azt tanítják, hogy csúcstörléssel hogyan mutatható ki a Hamilton-út/kör nemléte; ha a gráfban van Hamilton-kör, akkor tetszőleges n csúcs (és az azokhoz tartozó élek) törlésével a gráf legfeljebb n komponensre eshet szét (ez fordítva nem igaz, lásd; Petersen-gráf), út esetén pedig n+1 komponens engedélyezett (ez sem igaz fordítva; vegyünk egy háromszöggráfot, és mindegyik csúcsáról "lógassunk le" egy-egy csúcsot).

Tehát a feladat: keresnünk kell n darab mezőt/csúcsot, amik törlése után a sakktábla/gráf n+1 darab táblarészre/komponensre esik szét, és ilyet nem is nehéz találni; ha az előző hozzászóló ábráját vesszük, akkor ott töröljük a középső 4-est és az összes 3-ast, ekkor 5 mezőt/csúcsot töröltünk, és kaptunk 6 izolált mezőt/pontot és azt a 2-4-2-4 kört, amit kiemelt a válaszoló. Ezzel 7 táblarészre/komponensre sikerül szétvágni s sakktáblát/gráfot, de a fenti tétel alapján, ha lenne benne Hamilton-út, akkor csak 6-ra eshetett volna szét legfeljebb, így nem járható be lóugrásban. Ebből következően Hamilton-kör sincs benne, vagyis nem járható be úgy, hogy az utolsó mezőről az elsőre visszajussunk.

Utolsó:

Az első féle megoldás, amit leírtál elég gyenge lábakon áll. Valóban, a középső mezőből négy él megy 2-fokú csúcsokba, viszont ez nem jelenti, hogy mind a négy, vagy akár csak 3 élet is használni kell belőle.

Legyen a négy mező, ami ehhez a (N) csúcshoz kapcsolódik K1,K2,K3,K4. Elindulunk K1-ből, de nem n-be lépünk, hanem a másik élen lépünk tovább, majd lépkedés után K2-be jutunk, onnan N-en keresztül K3-ba, és onnan tovább eljutunk majd K4-be a másik (nem N-be vivő) élén keresztül. És lám, csupán egyszer haladtunk át N-en. Ha zárni akarnánk a kört, akkor kéne ismét N-en keresztülmenni, de ez nem feltétel. A második verzió mondjuk jó lehet, és tételt alkalmaztál, szóval "szebb" megoldás, mint mondjuk az enyém :)

Igazad van, erre nem gondoltam. Viszont, ha jól sejtem, ezt az esetet leszámítva mindig kellene 2-nél több élt használni, erről pedig látszik, hogy nem jó megoldás. Mindenesetre köszönöm a kiigazítást :)

A másik megoldás biztosan jó, mivel nekem is volt ez feladat, és max pontra értékelte a gyakvezető.