WikiSysop: bnz

2022-03-24T04:59:04Z

bnz

←Starija inačica		Inačica od 04:59, 24. ožujka 2022.
Redak 1:		Redak 1:
	~~<!--'''Problem osam topova'''-->'''~~Problem osam topova''' ili samo '''problem topova''' poznati je kombinatorni problem [[šahovska matematika\|šahovske matematike]]. Autor problema je [[Engleska\|engleski]] matematičar i sastavljač brojnih zagonetki [[Henry Dudeney]].		Problem osam topova''' ili samo '''problem topova''' poznati je kombinatorni problem [[šahovska matematika\|šahovske matematike]]. Autor problema je [[Engleska\|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?		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?

WikiSysop: Bot: Automatski unos stranica

2021-11-03T00:38:04Z

Bot: Automatski unos stranica

Nova stranica

'''Problem osam topova''' ili samo '''problem topova''' poznati je kombinatorni problem [[šahovska matematika|šahovske matematike]]. Autor problema je [[Engleska|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 [[Kula|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 [[Množenje|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>8 \cdot 7 \cdot 6 \cdot ... \cdot 2 \cdot 1</math> što zapisujemo kao <math>8!</math> (čitaj: osam [[faktorijel]]a).

U slučaju kada broj topova ne mora odgovarati broju polja i stupaca (ploča <math>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>A, B, C, ..., H</math>, a redovi brojevima <math>1, 2, 3, ..., 8</math>. Tada 3 slova od 8 možemo grupirati na <math>\frac{8!}{(8-3)!}</math> <math>=8 \cdot 7 \cdot 6=336</math> načina. No, svaku smo kombinaciju brojili <math>3!</math> puta pa ukupan broj dijelimo tim brojem. I sada, za svaku tu kombinaciju imamo opet <math>\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>t</math> topova na ploči <math>n \cdot n</math>, a ona glasi: <math>(\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>2n-1</math> drugih polja. Zbog toga, sljedeći top ima na raspolaganju <math>n^2-1(2n-1)</math> polja, treći <math>n^2-2(2n-1)</math> polja, itd. Dobivamo formulu
<math> \sum_{t=1}^{t} n^2-(t-1)(2n-1)</math>.

Ovo očito stvara zanimljivu vezu:
<math>(\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>t</math> <math>\le </math> <math>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>k \cdot m</math>). Tada za prebrojavanje koristimo topovski polinom ([[Engleski jezik|eng.]] rook polynomial).

[[Kategorija:Problemski šah]]

Problem osam topova - Povijest promjena

WikiSysop: bnz

WikiSysop: Bot: Automatski unos stranica