Zbiór zadań. Rozwiązanie zadania

Zbiór zadań, (zadania różne)

Zadanie 219

Na ile sposobów można ustawić dwie nierozróżnialne wieże na szachownicy 8 × 8 tak, aby się wzajemnie nie atakowały?

Rozwiązanie

Ogólnie dla n-wymiarowej szachownicy i k nierozróżnialnych wież, jeśli k = n, to ustawienia k wież spełniających warunki zadania sprowadza się do ustalenia numerów kolumn od 1 do k, na których znajdują się wieże należące także do wiersza o numerze odpowiednio 1, 2, ... , k. Liczba sposobów jest w tym przypadku równa liczbie permutacji zbioru k-elementowego, czyli k!.
Dla ogólnego przypadku k ≤ n, ustalamy k wierszy i k kolumn, w których mają być ustawione wieże. Możemy to uczynić na ${(\begin{matrix} n \\ k \end{matrix})}^{2}$ sposobów. Następnie na szachownicy utworzonej z pól znajdujących się na przecięciu wybranych wierszy i wybranych kolumn ustawiamy k wież spełniających warunki zadania. Można to zrobić na k! sposobów.
Łączna liczba sposobów ustawień k nierozróżnialnych wież na szachownicy n-wymiarowej równa jest ${(\begin{matrix} n \\ k \end{matrix})}^{2} \cdot k!$ .

W naszym przypadku mamy ${(\begin{matrix} 8 \\ 2 \end{matrix})}^{2} \cdot 2! = 1568$ .

Zadanie można rozwiązać w prostszy sposób, należało zauważyć, że jeśli jedną wieżę ustawimy na dowolnym polu, to drugą wieżę możemy ustawić na dowolnym polu szachownicy o wymiarze o jeden mniejszej. Stąd liczba sposobów równa jest $\frac{8^{2} \cdot 7^{2}}{2} = \frac{3136}{2} = 1568$ .

powrót do zbioru zadań | wersja do druku << poprzednie zadanie następne zadanie >>