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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 8\cdot 7\cdot 6\cdot ...\cdot 2\cdot 1} što zapisujemo kao Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 8!} (čitaj: osam faktorijela).
U slučaju kada broj topova ne mora odgovarati broju polja i stupaca (ploča Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle A,B,C,...,H} , a redovi brojevima . Tada 3 slova od 8 možemo grupirati na Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\frac {8!}{(8-3)!}}} Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle =8\cdot 7\cdot 6=336} načina. No, svaku smo kombinaciju brojili Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 3!} puta pa ukupan broj dijelimo tim brojem. I sada, za svaku tu kombinaciju imamo opet Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\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 Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t} topova na ploči Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n \cdot n} , a ona glasi: Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (\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 Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2n-1} drugih polja. Zbog toga, sljedeći top ima na raspolaganju Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n^2-1(2n-1)} polja, treći Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n^2-2(2n-1)} polja, itd. Dobivamo formulu Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{t=1}^{t} n^2-(t-1)(2n-1)} .
Ovo očito stvara zanimljivu vezu: Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (\frac{n!}{(n-t)!})^2 \cdot \frac{1}{t!}=\sum_{t=1}^{t} n^2-(t-1)(2n-1)} za sve prirodne brojeve Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t} Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \le } Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k \cdot m}
). Tada za prebrojavanje koristimo topovski polinom (eng. rook polynomial).