Ugrás a tartalomhoz

Matematikai mozaik

Andrásfai Béla, Bakos Tibor, Bognár Jánosné, Bognár Mátyás, Gallai Tibor, Hódi Endre, Laczkovich Miklós, Molnár Ferenc, Reimann István, Rényi Alfréd, Révész Pál, Rónyai Lajos, Surányi János, Vadkerty Tibor, Varga Tamás

Typotex

MATEMATIKA A SAKKTÁBLÁN

MATEMATIKA A SAKKTÁBLÁN

RÉVÉSZ, PÁL


A matematikai gondolkozás és a sakkjátékban szükséges gondolkodás hasonlósága valószínűleg mindenki számára nyilvánvaló. Mindkettő világos logikai készséget és nagyfokú kombináló képességet igényel. Ez a hasonlóság felveti a kérdést, hogy lehet-e a sakkjátékban matematikai módszereket használni, lehetséges-e megtalálni a legjobb stratégiát, vagy például sakkrejtvények megoldásában használhatók-e matematikai módszerek.

Különösen reményt keltő ebből a szempontból a matematika egy viszonylag új ágának, a játékelméletnek a kialakulása. Ez azt a feladatot tűzte maga elé, hogy általános módszereket adjon annak eldöntésére, hogy egyes játékokban vajon létezik-e valamelyik játszó fél számára nyerő stratégia, illetve hogyan tudják az egyes játékosok megtalálni a legjobb stratégiát. (Megemlítjük, hogy a játékelmélet haszna nem elsősorban az egyes játékok analízisében, hanem a matematikai statisztikában, a matematikának az alkalmazások szempontjából egyik legfontosabb fejezetében mutatkozik meg.) A játékelmélet eredményeiből eddig nem sikerült érdemleges következtetést levonni a sakkjátékra vonatkozóan. (Még arra a két kérdésre sem ismeretes a válasz, hogy létezik-e valamelyik félnek nyerő stratégiája, vagy hogyha egyik fél sem csinál hibát, akkor a játék eredménye döntetlen lesz-e?)

Ennek elsősorban az az oka, hogy a sakkjátékban igen nagyszámú kombinációt kellene áttekinteni. Ilyen nagyszámú eset áttekintése még a legmodernebb elektronikus számítógépek segítségével is lehetetlen. Megoldható feladat olyan elektronikus számítógép konstruálása, amely alkalmas 2 vagy 3 lépéses sakkfeladványok megoldására. Olyan sakkozó gép is konstruálható, amely két lépésben nem néz el tisztet, de természetesen egy ilyen gép kikaphat jobb sakkozótól.

A sakkjátéknál fellépő lehetőségek számát jellemzi, hogy mivel az első alkalommal mindkét játékos lehetséges lépéseinek száma 20, így miután mindkét játékos egy lépést tett, a lehetséges helyzetek száma 400. Amint az ellenőrizhető, a világos második lépése utáni lehetséges helyzetek száma 5206. (Itt az esetek összeszámlálásakor nem vettük külön esetként figyelembe azt, hogy egy állás több módon is létrejöhet. Így pl. az e4–e5–Hc3 és a Hc3–e5–e4 eseteket azonosaknak tekintjük. Ha ezeket különbözőknek tekintjük, az 5206-nak közel kétszeresét kapjuk.)

Valójában azt mondhatjuk, hogy a matematika szerepe a sakkjátékban igen minimális. (Más kérdés az, hogy a matematikával való foglalkozás útján szerzett kombinatív készség a sakkjátékban igen jól használható.) Érdekesebb a fordított kérdés: milyen szerepe van a sakknak a matematikában, pontosabban: milyen matematikai problémák vetődnek fel a sakkjátékkal kapcsolatban. Most ezzel az utóbbi kérdéssel foglalkozunk.

A monda szerint már a sakkjáték felfedezője is felvetett egy matematikai problémát az őt megjutalmazni kívánó uralkodónak. Ugyanis jutalmát búzaszemekben kérte, mégpedig úgy, hogy tegyen az uralkodó a sakktábla első mezőjére egy búzaszemet, a következőre kettőt, az azután következőre négyet és így tovább, mindig kétszer annyi szemet, mint amennyi az előzőn volt, végig a 64 mezőn. A történet szerint az uralkodó felháborodott, hogy a feltaláló ilyen „csekélységet” kér jutalmul, de amikor hozzákezdett a számoláshoz, kiderült, hogy a kérést nem tudja teljesíteni, ennyi búza az egész világon nem létezik.

Próbáljuk meg a számítási munkát mi elvégezni az uralkodó helyett! A sakktábla egyes mezőire jutó búzaszemek száma 1, 2, 4, 8, 16, …, 2^(63)

2 63 . Így a szükséges búzaszemek száma:

1+2+4+8+16+…+2^(63).
1 + 2 + 4 + 8 + 16 + + 2 63 .

Az összeg kiszámításához csak azt kell észrevennünk, hogy a sakktábla első k

k kockájára lerakott búzaszemek számának összege eggyel kevesebb, mint a (k+1) ( k + 1 ) -edik mezőre lerakott búzaszemek száma, azaz

1+2+4+8+16+…+2^(k–1)=2^k–1.
1 + 2 + 4 + 8 + 16 + + 2 k 1 = 2 k 1 .

Így

1+2+4+8+16+…+2^(63)=2^(64)–1.
1 + 2 + 4 + 8 + 16 + + 2 63 = 2 64 1 .

Megemlítjük, hogy 2^(64)

2 64 egy húszjegyű szám.

Egy másik, a sakktáblával (de még nem a sakkfigurákkal) kapcsolatos feladat Neumann Jánostól származik. Tegyük fel, hogy van egy sakktáblánk és egy olyan dominókockánk, amely a sakktábla két, egymás melletti mezőjét képes lefedni. Vágjuk ki a sakktábla két ellentétes sarkán lévő mezőket (pl. a1-et és h8-at), kérdés, a megmaradó tábla lefedhető-e dominókkal úgy, hogy minden mező egyszer és csak egyszer legyen lefedve.

Ha valaki megpróbálkozik a feladat elvégzésével, azt fogja tapasztalni, hogy 30 dominó elhelyezése után két, nem egymás melletti lefedetlen mező marad, amelyeket már egy 31-edik dominóval nem tud lefedni. Természetesen kérdés, hogy ez a próbálkozó ügyetlensége miatt van-e, vagy a feladat tényleg megoldhatatlan. A következő szellemes ötlettel belátható, hogy a feladatot valóban lehetetlen megoldani. Minden egyes dominó a sakktáblának egy fekete és egy fehér mezőjét fogja lefedni, viszont a két kivágott kocka mindegyike fehér (vagy mindegyike fekete). Így a feladat nyilvánvalóan megoldhatatlan. Ugyanígy megoldhatatlan a dominókkal való lefedés, ha bármely két olyan mezőt vágunk ki, amely egyszínű. Valamivel nehezebb belátni, hogy ha két különböző színű kockát vágunk ki a sakktábláról bárhonnan, akkor a lefedés megoldható.

A sakkfigurák közül talán legegyszerűbb a bástya lépéseinek áttekintése. Foglalkozzunk először a következő kérdéssel: hogyan lehet egy sakktáblára bástyákat elhelyezni úgy, hogy közülük bármely kettő ne üthesse egymást, azaz hogy bármely két bástya különböző sorban és különböző oszlopban legyen. Nyilvánvaló, hogy nyolc bástya elhelyezhető ily módon a sakktáblán (pl. úgy, hogy a tábla valamelyik átlójára tesszük a bástyákat), de nyolcnál több már nem. Kérdezzük, hogy hány különböző módon lehet nyolc bástyát elhelyezni a sakktáblán úgy, hogy ne legyen kettő, amelyik üti egymást. A feladat megoldása meglepően nagy szám: 40 320

40 320 . A következő módon lehet ezt belátni: ha nyolc bástyát elhelyezünk a sakktáblán úgy, hogy nincs kettő, amelyik üti egymást, akkor minden sorban lesz egy és csak egy bástya. Az első sor bármely helyére (tehát 8 hely mindegyikére) tehetjük az első bástyát. A második bástyát elhelyezzük a második sorba, vigyázva arra, hogy ne ugyanabba az oszlopba kerüljön, ahol az első bástya van; így a második bástyát 7 különböző helyre tehetjük (bárhova is tettük az elsőt). Ugyanígy látható, hogy a harmadik bástyát a harmadik sorba hatféleképpen lehet elhelyezni. Az eljárást folytatva adódik, hogy a 8 bástyát 8⋅7⋅6⋅5⋅4⋅3⋅2⋅1=40 320 8 7 6 5 4 3 2 1 = 40 320 -féleképpen lehet elhelyezni.

Meg kell jegyeznünk, hogy itt különböző elhelyezéseknek tekintjük pl. az a1 b2 c3 d4 e5 f6 g7 h8 és az a8 b7 c6 d5 e4 f3 g2 h1 elhelyezéseket, vagyis az olyan elhelyezéseket, amelyek egymásból a tábla elforgatásával, illetve tükrözéssel nyerhetők. Nehezebb az a kérdés, hogy hány lényegesen különböző elhelyezése létezik a nyolc bástyának, tehát olyan elhelyezése, amelyek között nincs kettő, mely forgatással, illetve tükrözéssel lenne nyerhető egymásból.

A királynővel kapcsolatos hasonló kérdésnél még az sem eleve világos, hogy hány királynő helyezhető el a sakktáblán úgy, hogy ne legyen kettő, amelyik üti egymást. Itt is belátható, hogy nyolcnál több királynő nem helyezhető el, de ennyi elhelyezése sem könnyű feladat. Hogy ez egyáltalán lehetséges, mutatja a következő példa: a1 b5 c8 d6 e3 f7 g2 h4 (lásd 1. ábra).

Könnyen ellenőrizhető, hogy a királynőket így elhelyezve valóban nincs kettő, amelyik ütné egymást. (Megjegyezzük, hogy a nem lényegesen különböző elhelyezések száma 92.) Nyilvánvaló, hogy ha ezekre a helyekre bástyákat vagy futókat rakunk, akkor a bástyáknak, illetve a futóknak olyan elhelyezését kapjuk, ahol nincs kettő, amely ütné egymást. Ha például ezekre a helyekre futókat rakunk, akkor elfér a táblára még egy futó (pl. c 2-re) (lásd 1. ábra), amely a már lerakott futók egyikét sem üti. Figyeljük meg azt is ezen a példán, hogy a nyolc vezér közül pontosan négy áll világos és négy sötét mezőn. Ellenőrizhető, hogy mind a 92 lehetséges elhelyezés rendelkezik az említett tulajdonsággal, azaz pontosan négy királynő áll világos mezőn.

Felvetődik a kérdés: hány királynő helyezhető el sötét mezőre úgy, hogy ne legyen kettő, amelyik üti egymást. Példánk mutatja, hogy négy bizonyosan. Kérdés, hogy négynél több elhelyezhető-e? Könnyen látható, hogy öt királynő elhelyezhető sötét mezőkön úgy, hogy ne üssék egymást, például a következő módon: a1 b6 d2 e7 g3 (2. ábra).

Nehezebb annak igazolása, hogy hat királynő elhelyezése már nem oldható meg.

Ezeknek a feladatoknak lényegében fordítottja a következő kérdés: mi a királynőknek az a minimális száma, amely elegendő ahhoz, hogy az egész táblát „lefogja”. Pontosabban, hány királynőt kell leraknunk a sakktáblára, ha azt akarjuk elérni, hogy minden mező a királynők legalább egyike által támadva legyen. Ezt a feladatot már 5 királynő el tudja látni, például a következő elhelyezésben: b4 d8 e3 f6 h2 (3. ábra).

(Ebben a példában a királynők mindegyike sötét mezőn áll.) Ellenőrizhető, hogy négy királynő nem elegendő az említett feladat végrehajtására. De ha csak azt tekintjük feladatunknak, hogy a királynőkkel a tábla világos mezőit lefedjük, akkor már elég négy királynő.

Futókkal kapcsolatban is felvethető, hogy hány futó helyezhető el a sakktáblán úgy, hogy ne legyen kettő, amelyik üti egymást. Elegendő kizárólag sötét futókkal foglalkoznunk. Könnyen látható, hogy legfeljebb 7 sötét futó helyezhető el így; ugyanis az (a7 b8), (a5 b6 c7 d8), (a3 b4 c5 d6 e7 f8), (a1 b2 c3 d4 e5 f6 g7 h8), (c1 d2 e3 f4 g5 h6), (e1 f2 g3 h4) és (g1 h2) „átlók” mindegyikén legfeljebb egy futó állhat. Hogy 7 futó valóban elhelyezhető, mutatja a következő példa: (a1 a3 a5 a7 h2 h4 h6) (4. ábra).

Összeszámolható az összes lehetséges elhelyezés száma is. Az a7 és b8 mezők egyikére (és csak egyikére) kell tennünk egy futót; ha a7-re tettük a futót, akkor h2-re is kell tennünk; ha h8-ra tettük, akkor g1-re is kell tennünk. Továbbá az a5 és d8 mezők egyikére kell tennünk futót. Aszerint, amint a5-re vagy d8-ra tettünk futót, futót kell tennünk h4-re, illetve e1-re. Hasonlóan az a3 és f8 mezők egyikére kell tennünk futót és ennek megfelelően h6-ra, illetve c1-re. Végül egy futót kell elhelyeznünk az a1 és h8 mezők egyikén. Ez a gondolatmenet mutatja, hogy a 7 világos futót 2⋅2⋅2⋅2=2^4=16

2 2 2 2 = 2 4 = 16 -féleképpen lehet a sakktáblán elhelyezni úgy, hogy ne legyen kettő, amelyik üti egymást. Fenti gondolatmenet világosan mutatja, hogy minden lehetséges elhelyezés olyan, hogy mind a 7 futó a tábla szélén áll.

Természetesen huszárokkal kapcsolatosan is felvethetők ilyen típusú kérdések. Nem nehéz arra válaszolni, hogy hány huszár helyezhető el a sakktáblán úgy, hogy ne legyen kettő, amelyik üti egymást, vagy hogy mi az a minimális számú huszár, amely elegendő ahhoz, hogy a tábla minden mezője a huszárok legalább egyike által támadva legyen.

Huszárokkal kapcsolatban nem teljesen evidens az sem, hogy egy huszárral a tábla bármely mezőjéről el lehet jutni a tábla bármely más mezőjére. Ez természetesen igaz, sőt igaz az is, hogy a sakktábla bejárható egyetlen huszárral úgy, hogy minden mezőt egyszer és csak egyszer érintünk. Például jó a következő út: a1 – c2 – e1 – g2 – h4 – g6 – h8 – f7 – d8 – b7 – a5 – b3 – c1 – e2 – g1 – h3 – g5 – h7 – f8 – d7 – b8 – a6 – b4 – a2 – c3 – b1 – a3 – b5 – a7 – c8 – b6 – a8 – c7 – e8 – g7 – h5 – g3 – h1 – f2 – d1 – e3 – f1 – h2 – f3 – d2 – c4 – b2 – a4 – c5 – d3 – f4 – e6 – d4 – f5 – d6 – e4 – f6 – g8 – h6 – g4 – e5 – c6 – e7 – d5 (5. ábra).

Természetesen egy sakkozót az a kérdés is érdekel, hogy egy adott helyről hány lépésben tud egy huszárral egy másik adott helyre eljutni. Ellenőrizhető, hogy bármely helyről bármely helyre legfeljebb hat lépésben el lehet jutni. (Nyilvánvaló, hogy pl. a1-ről h8-ra hatnál kevesebb lépésben nem lehet eljutni.)

A király szerepe főleg a végjátékban érdekes. Fontos kérdés például, hogy egy gyalogot a király „utol tud-e érni”. Ismeretes, hogy a „bemenő” gyalogot az ellenfél királya akkor és csak akkor tudja utolérni, ha a király benne van a gyalog négyzetében, vagyis abban a négyzetben, amelynek egyik csúcsa a gyalog és egyik éle az első, illetve nyolcadik vonal aszerint, amint a bemenő gyalog világos vagy sötét.

Kiszámítható, hogy egy adott helyről egy másik adott helyre hány lépésben tud eljutni a király. Érdekesebb az a kérdés, hogy egy adott helyről (pl. a kezdeti helyzetből) hányféleképpen tud minimális számú lépéssel eljutni egy másik adott helyre. Erre a kérdésre ad választ a 6. ábra.

Megjegyezzük, hogy ennek a táblázatnak képzési módja nagyon hasonlít az ún. Pascal-háromszög képzési módjához; ha a királynak csak átló-irányú lépéseket engednénk meg, a táblázat maga is hasonló lenne a Pascal-háromszöghöz. (Pontosan a Pascal-háromszöget kapnánk végtelen sakktábla használata esetén.) Az így adódó táblázatot a 7. ábra tartalmazza, a szaggatott vonalon belüli számok pontosan megegyeznek a Pascal-háromszög megfelelő elemeivel.