Kezdőlap


Cím:	A 4 x k méretű sakktábla bejárása lóugrással (Megjegyzés a P.26. sz. problémához)
Szerző(k):	Bakos Tibor , Surányi János , Tusnády Gábor
Füzet:	1970/január, 2 - 4. 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.

A P. 26. problémában^{$^{*}$} láttuk, hogy a $4 \times k$ méretű sakktáblának ( $k \geq 3$ , $k \neq 4$ ) lóugrással való bejárása csak úgy lehetséges, ha először egyik olyan résztartományát járjuk be, melyet a szélső sorok valamelyik színű mezői és a belső sorok ellentétes színű mezői alkotnak. Továbbá az egyik résztartományból a másikba való átlépés csak két belső mező közt lehetséges, és a bejárás kezdő- és végpontja szélső mezőn van.
Nem nehéz ezek ismeretében bejárási útvonalat kijelölni adott $k$ esetére, ezért csak olyan utasítás tekinthető érdekesnek, amely minden $k$ -ra érvényes, legalábbis valahonnan kezdve. Alább három ilyen bejárási utasítást adunk. Az 1. ábra színezése a tábla két résztartományát mutatja $k = 5$ esetére.

1. ábra

I. A táblát jobbról bal felé

4 \times 3

mezőnyi szelvényekre osztjuk, a balról esetleg maradó

1

vagy

2

oszlopot a velük szomszédos szelvényhez csatoljuk. Az első résztartomány bejárásában balról jobbra és szelvényről szelvényre haladunk. Az 1. szelvényt a

2 a

2 b

, illetve

2 c

ábra szerint járjuk be a számok sorrendjében,

k

-nak

3 j

3 j + 1

, illetve

3 j + 2

alakja szerint. A 2. szelvényt már egységesen bal alsó mezején kezdjük, a

2 a

ábrának a tábla hosszanti tengelyére vett tükörképe szerint járjuk be, majd váltakozva

2 a

-t és a tükörképét alkalmazzuk.
Sétánk felében, az utolsó szelvényben résztartományváltással a

2 d

ábra (vagy a tükörképe) szerint meg tudunk fordulni (a betűk rendjében), az előtte álló szelvényből pedig addigi útvonalunk tükörképén térünk vissza.
Eljárásunk

k = 3

és

k \geq 6

esetére használható.

2. ábra

II. Elég megadni az egyik tartomány egy záródó bejárását. Ha ugyanis egy ilyen bejárás van, akkor a másik tartomány egy bejárását kapjuk, ha az első bejárását tükrözzük a tábla két belső sorát elválasztó szimmetriatengelyre. Ezután egy olyan lépést veszünk, amely belső sorból belső sorba vezet, viszont mindegyik tartomány bejárásából elhagyjuk azt a lépést, amelyiknek egyik végpontja egybeesik a mondott lépéssel; így az egész tábla egy bejárását kapjuk.
Az egyik tartomány egy záródó bejárását összeállíthatjuk, ha

k

legalább 7, a

3 a

és

3 b

ábrából. Csak az egyik tartományhoz tartozó mezők középpontjait tüntettük fel, a lépéseket pedig a végpontokat összekötő szakaszokkal szemléltettük. A tábla egyik végét a

3 a

ábra szerint járhatjuk be, majd a

3 b

ábrán feltüntetett ,,halszálka minta'' szerű úton haladunk tovább a tábla végétől számított negyedik oszlopig; végül aszerint, hogy a tábla felső vagy alsó részébe értünk-e, a

3 a

ábrának a végpontjain átmenő egyenesre vagy ezen egyenes és a tábla szimmetriatengelyének metszéspontjára vett tükörképével zárhatjuk a bejárást. A

3 c

ábra

k = 9

-re, a

3 d

pedig

k = 10

-re mutatja be eljárásunkat.

k = 7

esetén nincs halszálkás része a bejárásnak.

3. ábra 4. ábra

Létezik záródó bejárás

k = 3

-ra is (4. ábra).
III. Más utasítást adunk az egyik résztartomány záródó bejárására, az előbb látottak szerinti további felhasználás céljára.
a) Páratlan

k

esetére egy szélső mezőről indulva lapos lóugrásokkal kétszer körülfutjuk a táblát ‐ vagyis minden mezőről a

2

oszloppal és

1

sorral odébb álló mezőre lépünk (a táblának természetesen vagy az alsó, vagy a felső felében) ‐, csupán a tábla szélső

2 - 2

oszlopában, a kanyarodva visszafordulásban iktatunk közbe 1‐1 magas ‐ azaz

1

oszloppal és

2

sorral távolodó ‐ lóugrást. Valóban, az alsó sornak egy páros sorszámú (legalább a

4

-ik) mezejéről így indulva jobbra, az első kanyarodásig a páros oszlopokban lépünk rá

1 - 1

mezőre, majd a magas lóugrás után a tábla felső felén visszajőve a páratlan oszlopokban

1

-re ‐

1

-re, és ismét az alsó féltáblára kanyarodva

k + 1

-edik mezőként az indulási oszlop belső sorbeli mezejére jutunk, hiszen váltakozva külső és belső sorbeli mezőkre léptünk, és

k + 1

páros. A második körülfutással ugyanígy (

2 k + 1

-edik mezőként) az indulási mezőre jutunk, eszerint útvonalunk záródik. Másrészt a bejárt mezők ‐ az alsó táblafél páros és a felső fél páratlan sorszámú oszlopbeli mezői az egyik résztartományt alkotják (más szóval azért, mert sohasem léptünk belső sorból belső sorba,

5 a

és

5 b

ábra).

5. ábra

b) Páros

k

esetén az első körülfutást ugyanígy végezzük. Ekkor azonban

k + 1

-edik mezőként az

I_{1}

indulási mezőre jutnánk, ezért az első körülfutást bevégző (tehát

2

. sorbeli) mezőből,

V_{1}

-ből jobbra fölfelé magas ugrással elérhető (tehát 4. sorbeli)

I_{2}

mezőből indítjuk a második körülfutást.

I_{2}

-re az első körülfutásban nem léptünk rá, ugyanis az alsó táblafélre való visszakanyarodás lépése jobbra lejt, az 1. oszlopból a

2

-ba visz, ezért az alsó és a felső táblafélen levő menetvonalrészek is ilyen eltolással állnak elő egymásból,

I_{1}

-ből a mondott

I_{2}

alatti mező.
A második körülfutás utolsó mezeje,

V_{2}

I_{2}

-től jobbra lejtő lapos ugrásnyira adódik, ezért belőle balra süllyedő magas lóugrással

I_{1}

-re jutunk, bejárásunk záródik; azonban ezek érdekében az indulás nem történhet a tábla utolsó oszlopából (

6 a

és

6 b

ábra).

6. ábra

Ez az eljárás minden megengedett

k

-ra érvényes.
A két résztartomány záródó bejárásai összekapcsolásának a II. és III. bejárási utasításban használt elvét Somorjai Gábor dolgozata tartalmazta, továbbá megadta

k

néhány páratlan értékére a lapos ugrásos záródó bejárást.

^{$^{*}$}Lásd a megoldást K. M. L. 39 (1969) 151. o.