Problem osam topova

Problem osam topova ili samo problem topova poznati je kombinatorni problem šahovske matematike. Autor problema je engleski matematičar i sastavljač brojnih zagonetki Henry Dudeney.

Osnovni problem glasi: Na koliko načina maksimalan broj istobojnih topova može stajati na šahovskoj ploči (8 × 8 polja), a da se ne napadaju?

Lagano možemo odgovoriti na pitanje maksimalnog broja topova. Kako imamo 8 redova i 8 stupaca, maksimalan je broj topova očito 8, a da imamo npr. 7 redova i 8 stupaca, maksimalan broj topova bio bi 7. Poopćimo ovo: ako imamo ploču n × n, maksimalan broj topova je upravo n, a ako imamo ploču k × m maksimalan broj topova je manji broj tog umnoška.

Nešto je teže odgovoriti na drugi dio pitanja, ali prebrojavanje nije komplicirano u ovom slučaju. Kako imamo 8 istobojnih topova, imamo 8 kombinacija za postavljanje tog topa u prvom stupcu. Prvi je red popunjen. Za stavljanje drugog topa u drugi stupac imamo 7 slobodnih polja. Ako nastavimo zaključivati doći ćemo do broja $8\cdot 7\cdot 6\cdot ...\cdot 2\cdot 1$ što zapisujemo kao $8!$ (čitaj: osam faktorijela).

U slučaju kada broj topova ne mora odgovarati broju polja i stupaca (ploča $n\cdot n$), prebrojavanje ipak nije onako jednostavno. Tada se koristimo idejama elementarne kombinatorike.

Uzmimo za primjer 3 istobojna topa na standardnoj šahovskoj ploči. Neka su stupci označeni slovima $A,B,C,...,H$, a redovi brojevima $1,2,3,...,8$. Tada 3 slova od 8 možemo grupirati na $\frac{8!}{(8-3)!}$ $=8\cdot 7\cdot 6=336$ načina. No, svaku smo kombinaciju brojili $3!$ puta pa ukupan broj dijelimo tim brojem. I sada, za svaku tu kombinaciju imamo opet $\frac{8!}{(8-3)!}$ kombinacija, no sada je poredak redova sada bitan (dvije dimenzije). To nam daje ukupan broj kombinacija koji iznosi 18,816. Dakle, imamo formulu za $t$ topova na ploči $n\cdot n$, a ona glasi: $(\frac{n!}{(n-t)!}{)}^2\cdot \frac{1}{t!}$.

Možemo postupiti i ovako. Problem ćemo riješiti na istom primjeru. Primijetimo da bilo gdje se nalazio, svaki top udara na $2n-1$ drugih polja. Zbog toga, sljedeći top ima na raspolaganju $n^2-1(2n-1)$ polja, treći $n^2-2(2n-1)$ polja, itd. Dobivamo formulu $\sum _{t=1}^t{n}^2-(t-1)(2n-1)$.

Ovo očito stvara zanimljivu vezu: $(\frac{n!}{(n-t)!}{)}^2\cdot \frac{1}{t!}=\sum _{t=1}^t{n}^2-(t-1)(2n-1)$ za sve prirodne brojeve $t$ $\le$ $n$.

Još teža varijacija problema je kada broj topova ne mora odgovarati broju redova i stupaca, ali niti broj redova ne mora odgovarati broju stupaca (ploča $k\cdot m$). Tada za prebrojavanje koristimo topovski polinom (eng. rook polynomial).