Problem osam topova

Izvor: Wikipedija
Prijeđi na navigaciju Prijeđi na pretraživanje

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 što zapisujemo kao (čitaj: osam faktorijela).

U slučaju kada broj topova ne mora odgovarati broju polja i stupaca (ploča ), 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 redovi brojevima . Tada 3 slova od 8 možemo grupirati na načina. No, svaku smo kombinaciju brojali puta pa ukupan broj dijelimo tim brojem. I sada, za svaku tu kombinaciju imamo opet kombinacija, no sada je poredak redova sada bitan (dvije dimenzije). To nam daje ukupan broj kombinacija koji iznosi 18,816. Dakle, imamo formulu za topova na ploči , a ona glasi: .

. Problem ćemo riješiti na istom primjeru. Primijetimo da bilo gdje se nalazio, svaki top udara na drugih polja. Zbog toga, sljedeći top ima na raspolaganju polja, treći polja, itd. Dobivamo formulu .

Ovo očito stvara zanimljivu vezu: za sve prirodne brojeve .


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 ). Tada za prebrojavanje koristimo topovski polinom (eng. rook polynomial).