Sakk az végesjáték?

Felteszem, hogy végesjáték alatt azt érted, hogy mindig létezik olyan lépés, amely után valamelyik játékos már nem tud szabályosan lépni. Ilyen szempontból nem véges játék, mivel ha a két király marad a táblán, akkor ők mindig tudnak szabályosan lépni, így a játék nem lesz véges minden esetben.

Ha a kérdéshez azt a kritériumot is hozzávesszük, hogy egy játék alatt ugyanaz az állás kétszer nem jöhet létre (például a huszárokkal nem lépegethetünk oda-vissza az elején), akkor nem nehéz belátni, hogy végesjátékról beszélünk; számoljuk ki, hogy a bábukat hányféleképpen lehet felpakolni a táblára; a készlet 32 bábuból áll, a sakktábla 64 mezőből.

-0 bábut triviálisan egyféleképpen tudunk felrakni.

-1 bábut (64 alatt a 32)-féleképpen tudjuk felrakni.

-2 bábut (64 alatt a (32 alatt a 2))*2!-féleképpen tudjuk felrakni. Először a 32 bábuból választunk ki 2-t, azoknak választunk 2 mezőt, és azokat az összes lehetséges módon felrakjuk a táblára.

-3 bábut (64 alatt a (32 alatt a 3))*3!-féleképpen lehet felpakolni.

Ebből már nem nehéz rájönni, hogy n bábut (64 alatt a (32 alatt az n))*n!-féleképpen lehet felrakni. Tehát a táblát

32

sum ((64 alatt a (32 alatt az n))*n!)

n=0

-féleképpen lehet megpakolni a bábukkal (a fenti esetben számoltakat összeadjuk).

Nyilván ez egy durva felső becslés a szabályos állások számára, de igazság szerint a feladat szempontjából lényegtelen, mert azt kell megmutatnunk, hogy véges sok állás keletkezhet csak. Értelemszerűen a fenti összeg véges, mivel természetes számokat adunk össze véges sokszor, tehát az összeg is véges lesz. Így ha állásismétlődés nem jöhet létre, akkor a játék egyszer véget fog érni.