Kezdőlap


Cím:	Királyok körei
Szerző(k):	Blázsik Zoltán
Füzet:	1995/szeptember, 338 - 340. 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 sakkjáték, a sakktábla és a figurák matematikai: kombinatorikai, gráfelméleti stb. problémák egész sorát vetik fel a legkönnyebbektől a legnehezebbekig. Ebben a tanévben néhány cikkel és néhány kitűzött gyakorlattal szeretnénk felkelteni az érdeklődést a téma iránt. A megoldásokhoz nem kell tudni sakkozni, elég logikusan gondolkozni!
$⋆$
A sakkjáték legfontosabb figurája a király. Egy királynak a sakktáblán azok a figurák a szomszédai, amelyek olyan mezőkön állnak, melyeknek van a király mezőjével közös határpontja. Képzeljük el, hogy elegendően sok királyunk van, s belőlük minél többet akarunk felállítani a sakktáblára, azzal a feltétellel, hogy egy zárt láncot (kört) alkossanak. Jelentse ez most azt, hogy bármely királynak pontosan két szomszédja van, és ha valamelyikük pl. jobbra ,,egy hírt a szomszédja fülébe súg'', akkor ha mindegyikük rendre ugyanezt teszi, mindenki tudomására jut, sőt a ,,hírt felröppentő'' balról vissza fogja hallani.
Vajon legfeljebb hány király állhat ,,körben'' a sakktáblán?
Mint hasonló kérdéseknél mindig, érdemes $n \times n$ -es ,,általánosított sakktáblán'' gondolkodni. Nyilvánvaló, hogy $2 \times 2$ -esen 3 király állhat körben; $3 \times 3$ -ason pedig legfeljebb $4$ , ‐ a pepita mezőszínezést használva ‐ a középső mező színével ellentétes mezőkön. Az első nekirugaszkodásra a 4, 5, 6 oldalú négyzetben úgy állítjuk fel a királyokat, hogy a tábla szélén, de ne sarokmezőn álljanak. Így rendre 8, 12, 16 királyt sikerül körbe állítanunk. De vajon nem lehet-e többet?
A $8 \times 8$ -as sakktábláig már csak egyetlen kisebb eset van. A $7 \times 7$ -es négyzetre az 1. ábra szerint $24$ királyt rakhatunk fel. Most tehát nem néggyel, hanem nyolccal nőtt a királyok száma. A hullámszerű konstrukció ,,kihasználja'' a tábla belsejét is. A $8 \times 8$ -asra azonban ugyanannyi hullám fér, tehát csak a hullám méreteinek növekedése a ,,nyereség''. Ezzel a módszerrel a klasszikus sakktáblára 30 királyt állíthatunk körbe.
Ne álljunk meg 8-nál!
A hullámok száma $n = 4 k + 3$ -nál $k$ , s ugyanennyi marad, ha az $n$ eggyel, kettővel vagy hárommal növekszik.
Emiatt ezzel a konstrukcióval kapott ,,királyi körökben'' a királyok száma:

\begin{matrix} \begin{matrix} \frac{n^{2}}{2} - \frac{1}{2}, & ha n \equiv 3 (mod 4), \\ \frac{n^{2}}{2} - \frac{n}{2} + 2, & ha n \equiv 0 (mod 4), \\ \frac{n^{2}}{2} - n + \frac{9}{2}, & ha n \equiv 1 (mod 4), \\ \frac{n^{2}}{2} - \frac{3 n}{2} + 7, & ha n \equiv 2 (mod 4) és n > 2. \end{matrix} \end{matrix}

Nem lehetnénk ügyesebbek?
Az világosnak tűnik, hogy ,,érdemes'' a tábla szélét kihasználni, és a problémát a belsejének felépítése jelenti. Próbálkozzunk rekurzívan!
Ha

n \geq 7

, akkor válasszuk ketté a táblát egy

(n - 4) \times (n - 4)

-es ,,centrumra'' és egy 2 mező szélességű ,,keretre''. A keret külső szélére ‐ kivéve a sarkokat ‐ helyezzünk el királyokat (

4 \cdot (n - 2)

db-ot). Tegyük fel, hogy a centrumban már létezik egy királyi lánc. Elég lenne ezután mindkét zárt láncot megbontani, ,,egy-két láncszemet kivenni, s összekötni a végeket''. Ekkor egy zárt láncot kapnánk, amely közel lenne az optimálishoz, ha a néggyel kisebb

(n - 4)

-re elég hosszú volt a kör.

7

-re ugyanazt kapjuk, mint korábban. Vajon a ,,klasszikus sakktáblán'' sem javul a helyzet? A 2. ábra szerint igen! Létezik 31 királyból álló kör!

n = 9

-re a centrum

5 \times 5

-ös. Most csak két láncszem ,,elvesztésével'' megy a két kör összekötése (8-ra egy, 7-re 0 király ,,veszett el'').
10-re a centrum

6 \times 6

-os. Ha a 16 hosszú kört a centrumban módosítjuk azzal, hogy az egyik királyt egy lépéssel beljebb helyezzük, akkor az összekapcsolódásnál fellépő veszteség újra csak 1 lesz. Később az összefűzésnél már nem veszítünk!
A 7, 8, 9, 10 oldalú sakktáblára most konstruált királyi körök (3. ábra) olyanok, hogy létezik egy ,,hullámcsúcsuk'', amelyhez a további kör veszteség nélkül kapcsolható. Ez a jó tulajdonság később is megmarad.
Folytatva az eljárást, a következő eredményt kapjuk:

\begin{matrix} \begin{matrix} \frac{n^{2}}{2} - \frac{1}{2}, & ha n \equiv 3 (mod 4) . \\ \frac{n^{2}}{2} - 1, & ha n \equiv 0 (mod 4) ésn > 4;n = 4-re 8. \\ \frac{n^{2}}{2} - \frac{5}{2}, & ha n \equiv 1 (mod 4) ésn > 5;n = 5-re 12. \\ \frac{n^{2}}{2} - 3, & ha n \equiv 2 (mod 4) ésn > 6;n = 2-re 3,n = 6-ra 16. \end{matrix} \end{matrix}

Összehasonlítva azt tapasztaljuk, hogy a második konstrukció lényegesen jobb, mint az első. Nem tudnánk beférkőzni a királyok közé?

⋆

Cikkünk nem zárja le a problémakört, érdemes rajta tovább gondolkodni. Hozzászólásaikat a szerkesztőség címén várja a szerző:

Blázsik Zoltán