Szachownice - klasa abstrakcji

undothefuture · Post autor: **undothefuture** » 4 mar 2013, o 18:23

1. Na ile sposobów można ustawić 2 króle na szachownicy n x m tak, aby nie stały na sąsiednich polach?

2. Ile jest wszystkich prostokątów, które można wykroić z szachownicy o wymiarach n x n? (chodzi oczywiście o dowolne cięcia wzdłuż linii szachownicy)

Errichto · Post autor: **Errichto** » 4 mar 2013, o 18:35

1. Rozważ przypadki gdy pierwszy król jest w rogu szachownicy, na brzegu albo w środku. Potem mamy różną dla każdego przypadku liczbę sposobów ustawienia drugiego króla. Na koniec wynik podziel przez 2 - każde rozwiązanie policzyłeś dwukrotnie (dlaczego?).
2. Wybierasz dwie różne liczby z numerów wierszy - będą to góra i dół prostokąta. To samo z kolumnami. Pamiętaj o odjęciu kilkukrotnie policzonych rozwiązań.