Hányféleképpen helyezhető el két azonos színű (egyforma) futó a 8$\times $ 8-as sakktáblán úgy, hogy ne üssék egymást (azaz ne legyenek egy átlós irányú egyenesen)?
 
A tábla minden mezőjére ráírjuk, hogy arról a mezőről a futó hány más mezőt nem támad. Ezt könnyű elvégezni két észrevétel miatt: 1. Először azt számoljuk ki, hogy az adott mezőről futókkal hány másikra lehet átlépni, és ezt az értéket kell kivonnunk 63-ból. 2. Kihasználhatjuk a tábla középpontja körüli $ 90^\circ $-os forgatási és az átlókra való tükrözési szimmetriát, és így elég 10 mezőnél kiszámolni az értékeket. Ennyi helyre léphet át a futó Ennyi mezőt nem támad
7 | 7 | 7 | 7 | 56 | 56 | 56 | 56 | 56 | 56 | 56 | 56 | |||||
9 | 9 | 9 | 56 | 54 | 54 | 54 | 54 | 54 | 54 | 56 | ||||||
11 | 11 | 56 | 54 | 52 | 52 | 52 | 52 | 54 | 56 | |||||||
13 | 56 | 54 | 52 | 50 | 50 | 52 | 54 | 56 | ||||||||
56 | 54 | 52 | 50 | 50 | 52 | 54 | 56 | |||||||||
56 | 54 | 52 | 52 | 52 | 52 | 54 | 56 | |||||||||
56 | 54 | 54 | 54 | 54 | 54 | 54 | 56 | |||||||||
56 | 56 | 56 | 56 | 56 | 56 | 56 | 56 |
Most már ha elhelyezzük az ,,első futót'', akkor le tudjuk olvasni, hogy a ,,másodikat'' hányféleképpen helyezhetjük el. Az ,,elsőt'' a 64 mező bármelyikére tehetjük, így az ,,első'' és a ,,második'' futót összesen annyiféleképpen helyezhetjük el, amennyi a felírt 64 szám összege. Ez:
Valójában pont feleennyi lehetőség van, mert nincs ,,első'' és ,,második'' futó, hanem két egyforma futó van. Tehát a megoldás: 1736. Megjegyzés. Általánosíthatjuk a feladatot $ 2n\times 2n-$es táblára! Tekintsük az alábbi ábrát:
A $ 2n\times 2n$-es tábla mezőinek száma $ 4n^2$. Az egyes rétegekben lévő mezők száma rendre $i $=1, 2, ..., $n$ esetén:
Az $i$-edik rétegben álló futó (tetszőleges mezőn állva) rendre a következő számú mezőt foglalja el:
tetszőleges $i\mbox{-re: }2n+\left( {i-1} \right)\cdot 2$
Javasoljuk, hogy rajzolja fel az olvasó az $i$-edik réteg tetszőleges mezőjén álló futó által elfoglalt mezőket! A megoldások $M$ száma az előzőek alapján --- az első megoldás gondolatmenetét követve ---:
Felhasználva, hogy $\sum\limits_{i=1}^n {i=\frac{n\left( {n+1} \right)}{2}} $ és
Azonos átalakítások után az
eredményhez jutunk. Természetesen $n=4$-re a már ismert
megoldást kapjuk. A továbbiakban egy rekurzióra épülő általános megoldást is bemutatunk. Legyen a megfelelő elhelyezések száma $n\times n$-es tábla esetén $f\left( n \right)$. Jelöljük továbbá $g\left( n \right)$-nel azon elhelyezések számát, amelyekben mindkét futó a tábla szélső mezőjén áll, $h\left( n \right)$ pedig jelölje azoknak a megfelelő elhelyezéseknek a számát, amelyekben pontosan az egyik futó áll a tábla szélső mezőjén. Tekintsük a következő ábrát:
Ha az először letett futó sarokmezőre kerül, akkor $g\left( {n+2} \right)$-t tekintve a második futó már csak $ 4n+2$ helyre kerülhet. Ha viszont az ,,első'' futó nincs sarokmezőn --- ekkor $ 4n$ különböző mezőre kerülhet ---, akkor a második futó $ 4n+1$ darab mezőre állhat. Ezek alapján
mert minden esetet kétszer vettünk számításba. Hasonló gondolatmenet alapján adódik a $h\cdot \left( {n+2} \right)$-re kapható $h\left( {n+2} \right)=4n^3$ formula, hiszen ha az egyik futó sarokmezőn áll, akkor a megfelelő esetek száma $ 4\left( {n^2-n} \right)$, ha pedig nem áll futó a sarokban, akkor $ 4n\left[ {n^2-\left( {n-1} \right)} \right]$ az elhelyezések száma. Ábránk és az eddigiek alapján nyilvánvaló, hogy $f\left( {n+2} \right)=f\left( n \right)+g\left( {n+2} \right)+h\left( {n+2} \right)$. Felhasználva, hogy $g\left( {n+2} \right)=2\left( {4n^2+5n+2} \right)$ és $h\left( {n+2} \right)=4n^3$, $f\left( {n+2} \right)$-re
adódik. Ezzel $f\left( n \right)$ értékét sikerült rekurzív módon megadni. Ha például $f\left( 8 \right)$-at akarjuk kiszámítani (az eredeti feladat), akkor $f\left( 2 \right)=4$ alapján $f\left( 4 \right)=32+32+20+4+4=92,$ továbbá $f\left( 6 \right)=256+128+44+92=520,$ így
az első megoldásnak megfelelően. Megjegyezzük, hogy az $f\left( n \right)$-re kapott formula természetesen páratlan $n $értékek esetén is helyes, a rekurzió ,,kezdőértéke'' $f\left( 1 \right)=0$. Próbáljuk most meg egy lépésben megadni $f\left( {n+1} \right)$ értékét $f\left( n \right)$ segítségével! Alkalmazzuk a következő táblára rekurzív megadásunk gondolatmenetét:
Ha mindkét futó az L alakú tartomány mezőin áll, akkor a megfelelő elhelyezések száma: $\frac{1\cdot 2n+2n\cdot \left( {2n-1} \right)}{2}=2n^2$, ha pedig pontosan az egyik futó áll az iménti tartomány egyik mezőjén, akkor
számú jó elhelyezés létezik. Az előzőek alapján ekkor
Tehát bármely $\left( {n+1} \right)\times \left( {n+1} \right)$-es táblára igaz, hogy a megfelelő futóelhelyezések számára teljesül az
összefüggés. Kapott eredményünk lehetőséget nyújt arra, hogy $f\left( n \right)$ értékét zárt alakban kapjuk meg. Bebizonyítjuk, hogy bármely $n\ge 1$ esetén
A bizonyításhoz vezessük be a következő jelölést:
Az $f\left( {n+1} \right)$-re kapott formula alapján
A felírt $n$ darab összefüggés megfelelő oldalainak összegzésével az
egyenlőséghez jutunk, ahol $f\left( 1 \right)=0$. Felhasználva, hogy
$S_n^{\left( 2 \right)} =\frac{n\left( {n+1} \right)\left( {2n+1} \right)}{6}$ és
azonos átalakítások után a bizonyítandó
formulához jutunk, ahonnan $\left( {n+1} \right)$ helyett $n$-et írva
adódik. Végezetül egy további általánosítási lehetőséget vizsgálunk meg. Kérdésünk az, hogy az $n\times k-$as táblán ($n$ darab oszlop és $k$ darab sor) $n\ge k$ esetén mennyi a megfelelő futóelhelyezések száma. Az $f\left( {n+1} \right)$-re kapott formula esetében alkalmazott gondolatmenet alapján:
azaz
Eredményünk alapján
A felírt egyenlőségek összegzésével
adódik, ahonnan rendezéssel
Ha tehát $n\ge k$ és $n=k+l$ jelöléssel élünk, akkor
Formulánkba $f\left( {k,k} \right)=\frac{\left( {k-1} \right)\cdot k\cdot \left( {3k^2-k+2} \right)}{6}$-ot helyettesítve azonos átalakítások után az
eredményt kapjuk. Ezzel feladatunkat bármilyen $n\times k$-as táblára megoldottuk, hiszen $k>n$ esetén (a tábla szimmetriája miatt) $n$ és $k$ szerepcseréjével jutunk a megfelelő eredményhez.