3340. Elementi kombinatorike

TEKST ZADATKA

Na koliko načina se na šahovsku tablu može postaviti 8 različitih topova tako da se nikoja dva međusobno ne tuku (nikoja dva se ne nalaze u istoj vrsti ili istoj koloni)?

REŠENJE ZADATKA

Šahovska tabla ima 8 vrsta i 8 kolona, odnosno ukupno $8 \cdot 8 = 64$ polja. Pošto se topovi ne smeju tući, u svakoj vrsti i svakoj koloni može se nalaziti najviše jedan top.

Pošto u zadatku imamo 8 različitih topova, možemo ih postavljati na tablu jedan po jedan i pratiti broj slobodnih polja za svaki sledeći top.

Prvi top možemo postaviti na bilo koje od 64 polja na tabli. Dakle, za njega imamo na raspolaganju 8 vrsta i 8 kolona.

n_1 = 8 \cdot 8 = 64

Kada postavimo prvi top, on 'zauzima' svoju vrstu i svoju kolonu. Za drugi top preostaje tabla od 7 slobodnih vrsta i 7 slobodnih kolona na koje ga možemo postaviti.

n_2 = 7 \cdot 7 = 49

Slično, treći top ne sme biti u vrstama i kolonama gde su prva dva topa. Za njega ostaje slobodno 6 vrsta i 6 kolona.

n_3 = 6 \cdot 6 = 36

Nastavljajući ovaj postupak, svaki sledeći top ima po jednu vrstu i kolonu manje na raspolaganju. Za poslednji, osmi top, ostaće samo jedno slobodno polje (1 slobodna vrsta i 1 slobodna kolona).

n_8 = 1 \cdot 1 = 1

Prema pravilu proizvoda, ukupan broj načina da rasporedimo svih 8 topova dobijamo množenjem broja mogućnosti za svaki pojedinačni top.

N = n_1 \cdot n_2 \cdot n_3 \cdot \dots \cdot n_8

Zamenjujemo vrednosti koje smo dobili za svaki top u formulu.

N = (8 \cdot 8) \cdot (7 \cdot 7) \cdot (6 \cdot 6) \cdot \dots \cdot (1 \cdot 1)

Ovaj izraz možemo grupisati drugačije, tako što ćemo pomnožiti sve prve činioce iz zagrada, a zatim sve druge činioce.

N = (8 \cdot 7 \cdot 6 \cdot \dots \cdot 1) \cdot (8 \cdot 7 \cdot 6 \cdot \dots \cdot 1)

Znamo da je proizvod prirodnih brojeva od 1 do 8 jednak faktorijelu broja 8, koji označavamo sa $8! .$ Time dobijamo konačno rešenje.

N = 8! \cdot 8! = (8!)^2

136