Cím: Egy feladat végleges megoldása
Szerző(k):  Bartók-Csató György 
Füzet: 1983/május, 196 - 199. oldal  PDF  |  MathML 
Témakör(ök): Szakmai cikkek

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.

Csákány Antal‐dr. Vajda Ferenc: Játékok számítógéppel című könyvében találtam a következő feladatot:

 

Adott egy 4×3-as sakktábla (I. ábra), a két alapsoron három fehér, illetve három fekete huszár áll, melyek lóugrásban léphetnek a táblán. A feladat: Cseréljük meg a világos és sötét lovakat a lehető legkevesebb lépésben.
 

1. ábra
 
Egy mezőn egyszerre csak egy huszár állhat, de bármelyik figurával bármikor léphetünk, azaz nem kötelező felváltva lépnünk, mint a sakkban.
A könyv szerint a feladat 1974-ben jelent meg az USA-ban. Kezdetben 26, azután 18, végül 16 lépéses megoldást találtak rá. Most bebizonyítjuk, hogy 16-nál kevesebb lépés nem elegendő a feladat végrehajtására.
Tekintsük a tábla egy átrendezését (2. ábra). A mezőket kis körök jelzik. Most is alaphelyzetben vannak a figurák, és egy körrel pontosan azok vannak összekötve, amelyeknek megfelelő mezőre az adott mezőről léphetünk.
 

2. ábra
 
Mindkét ábráról látható, hogy mindegyik lóval legalább kettőt kell lépnünk, hogy átjuthassunk a másik alapsorra. Elméletileg tehát 12 lépés mindenképpen szükséges ahhoz, hogy a lovak helyzetét megcseréljük.
Tekintsük most csak a fehér lovakat. Vizsgáljuk meg, hogy 6 lépésben átrakhatók-e az ellenkező alapsorba úgy, hogy mindegyik ló más-más mezőre kerüljön. Nézzük ehhez a 2. ábrát. Látható, hogy az Al és a Cl lovak két lépésben egyaránt csak a B4 mezőre juthatnak, így legalább az egyik lónak minimum 3 lépés kell. A világos lovaknak tehát összesen legalább 7 lépés kell, hogy eljussanak a negyedik sorra. Ugyanez igaz a sötét lovakra is, a feladat megoldásához minimum 14 lépés szükséges.
Most megmutatjuk, hogy 14 lépés nem elegendő. Ha van a lovaknak 14 lépéses cseréje, az az előzőek szerint csak úgy lehetséges, hogy 7-et lépünk a világos és 7-et a sötét figurákkal. Tekintsük most a világos lovakat. A lovak a 7 lépést háromféleképpen tehetik meg:
 

a) az A1-ló 3-at, a B1-ló 2-t, a C1-ló 2-t lép,
b) az A1-ló 2-t, a Bl-ló 3-at, a C1-ló 2-t lép,
c) az A1-ló 2-t, a B1-ló 2-t, a C1-ló 3-at lép.
 

A b) eset nem lehetséges, mert ekkor a lépések után mind a három ló a B4 mezőre kerülne. Ez az 1. vagy a 2. ábráról is leolvasható.
Vegyük észre, hogy mind az a), mind a c) esetben mindhárom világos ló útvonala és az a hely, ahová beérkezik, egyértelműen meghatározott. Ugyanis az a) esetben az Al-ló három lépésben pontosan a C4 mezőre jut az A1‐C2, C2‐A3, A3‐C4 lépésekkel. Ekkor a B1-ló két lépésben csak A4-re kerülhet, mégpedig a B1‐C3, C3‐A4 útvonalon. A Cl-ló útvonala és véghelyzete ugyanígy meghatározott: Két lépésben a C1‐A2, A2‐B4 lépésekkel a B4 mezőre kerül. A c) esetben világos lovak lépései a következők:
 

C1-ló: C1‐A2, A2‐C3, C3‐A4,
B1-ló: B1‐A3, A3‐C4,
Al-ló: A1‐C2, C2‐B4.
 

A világos lovakhoz hasonlóan a sötét lovak a következőképpen léphetnek:
 

d) az A4-ló 3-t, a B4-ló 2-t, a C4-ló 2-t lép,
e) az A4-ló 2-t, a B4-ló 3-t, a C4-ló 2-t lép,
f) az A4-ló 2-t, a B4-ló 2-t, a C4-ló 3-at lép.
 

Nyilvánvaló, hogy most az e) eset nem lehetséges. A sötét lovakra is igaz a d) és f) esetekben, hogy útvonaluk és véghelyzetük egyértelműen meghatározott. A d) esetben a sötét lovak lépései a következők:
 

A4-ló: A4‐C3, C3‐A2, A2‐Cl,
B4-ló: B4‐C2, C2‐Al,
C4-ló: C4‐A3, A3‐B1.
 

Az f) esetben pedig:
 

C4-ló: C4‐A3, A3‐C2, C2‐A1,
B4-ló: B4‐A2, A2‐C1,
A4-ló: A4‐C3, C3‐B l.
 

A világos lovaknak az a) esetbeli lépéseihez nem tartozhatnak a sötét lovaknak azok a lépései, amiket az f) eset tárgyal. Az A1-ló ugyanis így ugyanazon az útvonalon jutna a C4 mezőre, mint a C4 sötét ló az A1 mezőre, természetesen fordított irányban. Így valahol találkozniuk kellene, de ez a szabályok miatt lehetetlen, mivel egy adott mezőn egyszerre csak egy ló állhat. Ugyanígy a világos lovak c) eset által adódó lépéseihez nem tartozhatnak a sötét lovak d)-beli lépései.
Tehát a világos és sötét lovak 14 lépése, amely mint láttuk, egyértelműen meghatározott, kétféleképpen állhat elő: a világos lovak a)-beli lépéseihez a sötét lovak d)-beli lépései tartoznak, vagy a világos lovak c)-beli lépéseihez a sötét lovak f)-beli lépései tartoznak. Ez a két eset egymással szimmetrikus, így elég csak az egyiket, pl. az elsőt tárgyalni. (A szimmetria oka az, hogy ha a táblát 180∘-kal elforgatjuk, akkor az egyik esetből a másikhoz jutunk, ugyanis a világos és sötét lovaknak nincs kitüntetett szerepük egymáshoz képest.) Az ezek által meghatározott 14 lépés olyan időbeli sorrendjét kellene megtalálnunk, amely lejátszható, azaz kielégíti a feladat követelményeit. Megmutatjuk, hogy nincs ilyen sorrend. Ehhez tekintsük a 3. ábrát, ahol a figurák tervbe vett útvonalát is feltüntettük.
 

3. ábra
 
A B1 és a B4 mezőkön álló lovak kezdő lépéseinek egymáshoz viszonyított időbeli sorrendje szerint két eset lehetséges:
I. A B1-ló első lépése megelőzi a B4-ló első lépését. Ezután a lépés után a 3. ábra bal oldalán a következő helyzet áll elő: Az A4-lónak vagy A2-n vagy C1-en kell lennie, mert különben nem tudnánk a B1-lóval A4-re lépni. Ugyanakkor a C1-lónak B4-en kell már állnia, hiszen az A4-lóval A2-n keresztül Cl-re csak úgy tudunk eljutni, ha a C1-ló már belépett B4-re. De feltevésünk szerint a B4-ló még eredeti helyén áll ‐ ez ellentmondás, tehát nem tudjuk a figurákat ily módon a feladat követelményeinek megfelelően átrendezni.
II. A B4-ló első lépése megelőzi a B1-ló első lépését. Ekkor a 3. ábra jobb oldalát nézve szintén ellentmondásra jutunk. A feladatnak tehát nincs 14 lépéses megoldása.
Vizsgáljuk most meg, hogy megoldható-e a feladat 15 lépésben! Megmutatjuk, hogy ez is lehetetlen. Ha 15 lépésben megoldható volna a feladat, az csak úgy lehetséges, hogy vagy a világos lovakkal 7-et, a sötét lovakkal pedig 8-at lépünk, vagy a sötét lovakkal lépünk 7-et és a világos lovakkal 8-at. A szimmetria miatt elég belátnunk az első eset lehetetlenségét.
A sötét lovak elvileg hatféleképpen léphetnek 8-at:
 

a) az A4-ló 3-at, a B4-ló 3-at, a C4-ló 2-t lép,
b) az A4-ló 3-at, a B4-ló 2-t, a C4-ló 3-at lép,
c) az A4-ló 2-t, a B4-ló 3-at, a C4-ló 3-at lép,
d) az A4-ló 4-et, a B4-ló 2-t, a C4-ló 2-t lép,
e) az A4-ló 2-t, a B4-ló 4-et, a C4-ló 2-t lép,
f) az A4-ló 2-t, a B4-ló 2-t, a C4-ló 4-et lép.
 

Minden esetben megvizsgáljuk, hogy a sötét lovak pontosan 8 lépésben hogyan juthatnak át az első sorra.
Az a) esetben az A4-ló csak C1-re, a B4-ló csak B1-re, a C4-ló szintén csak Bl-re kerülhet.
A b) esetben az A4-ló csak C1-re, a B4-ló Al-re vagy C1-re, a C4-ló csak A1-re kerülhet.
A c) esetben az A4-ló csak B1-re, a B4-ló csak B1-re, a C4-ló csak A1-re kerülhet.
A d)‐e)‐f) esetekben az A4-ló csak B1-re, a B4-ló A1-re vagy C1-re, a C4-ló csak B1-re kerülhet.
Ezen állítások helyességének belátását az olvasóra bízzuk.
Mivel a sötét lovak közül mindegyik esetben kettő ugyanarra a mezőre jut, 8 lépésben akkor sem juthatnak át az első sorra, ha nincsenek is világos lovak a táblán. A feladat tehát 15 lépésben sem oldható meg.
Mivel 16 lépéses megoldást ismerünk (lásd alább), ezért ennek a feladatnak legkevesebb lépésszámú megoldása 16 lépéses.
A feladat egy 16 lépéses megoldása a következő: 1. A1‐C2, 2. C2‐A3, 3. C1‐A2, 4. B4‐C2, 5. A2‐B4, 6. A4‐C3, 7. C3‐A2, 8. A2‐C1, 9. C2‐A1, 10. B1‐C3, 11. C3‐A4, 12. A3‐C2, 13. C4‐A3, 14. A3‐B1, 15. C2‐A3, 16. A3‐C4.
 

Végül kitűzünk egy feladatot is: ha, úgy nehezítjük az eredeti feladatot, hogy a világos és sötét lovaknak felváltva, kell lépniük, akkor mennyi az a minimális Lépésszám, amellyel meg lehet cserélni a világos és sötét lovak helyzetét? Természetesen az eddigi követelményeink is érvényben maradnak.