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 [math]\displaystyle{ 8 \cdot 7 \cdot 6 \cdot ... \cdot 2 \cdot 1 }[/math] što zapisujemo kao [math]\displaystyle{ 8! }[/math] (čitaj: osam faktorijela).

U slučaju kada broj topova ne mora odgovarati broju polja i stupaca (ploča [math]\displaystyle{ n \cdot n }[/math]), 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 [math]\displaystyle{ A, B, C, ..., H }[/math], a redovi brojevima [math]\displaystyle{ 1, 2, 3, ..., 8 }[/math]. Tada 3 slova od 8 možemo grupirati na [math]\displaystyle{ \frac{8!}{(8-3)!} }[/math] [math]\displaystyle{ =8 \cdot 7 \cdot 6=336 }[/math] načina. No, svaku smo kombinaciju brojili [math]\displaystyle{ 3! }[/math] puta pa ukupan broj dijelimo tim brojem. I sada, za svaku tu kombinaciju imamo opet [math]\displaystyle{ \frac{8!}{(8-3)!} }[/math] kombinacija, no sada je poredak redova sada bitan (dvije dimenzije). To nam daje ukupan broj kombinacija koji iznosi 18,816. Dakle, imamo formulu za [math]\displaystyle{ t }[/math] topova na ploči [math]\displaystyle{ n \cdot n }[/math], a ona glasi: [math]\displaystyle{ (\frac{n!}{(n-t)!})^2 \cdot \frac{1}{t!} }[/math].

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

Ovo očito stvara zanimljivu vezu: [math]\displaystyle{ (\frac{n!}{(n-t)!})^2 \cdot \frac{1}{t!}=\sum_{t=1}^{t} n^2-(t-1)(2n-1) }[/math] za sve prirodne brojeve [math]\displaystyle{ t }[/math] [math]\displaystyle{ \le }[/math] [math]\displaystyle{ n }[/math].

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 [math]\displaystyle{ k \cdot m }[/math]). Tada za prebrojavanje koristimo topovski polinom (eng. rook polynomial).