Dwa króle na szachownicy

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
FaloZ
Użytkownik
Użytkownik
Posty: 12
Rejestracja: 30 wrz 2017, o 15:31
Płeć: Mężczyzna
Lokalizacja: Warszawa

Dwa króle na szachownicy

Post autor: FaloZ »

Na ile sposobów można ustawić dwa króle na szachownicy o wymiarach \(\displaystyle{ n}\) na \(\displaystyle{ m}\) tak, aby nie stały na sąsiadujących polach?

Znalazłem temat na forum z identycznym zadaniem: 337768.htm , ale wydaję mi się, że nie do końca rozumiem rozwiązania.

Sytuacja, gdy król stoi w rogu jest dla mnie jasna, bo szachownica jest wymiaru \(\displaystyle{ n imes m}\) i eliminujemy trzy pola oraz miejsce, na którym stoi król. Dla jednego rogu mamy zatem \(\displaystyle{ (mn-4)}\). Wynik mnożymy czterokrotnie z racji, iż szachownica posiada dokładnie \(\displaystyle{ 4}\) rogi.

Problem zaczyna się dalej. Sytuacja, kiedy król stoi przy krawędzi szachownicy jest prawie jasna. Przypadek \(\displaystyle{ (mn-6)}\) jest klarowny, bo mamy tutaj podobną sytuację jak w przypadku, gdy król stoi w rogu. Problem zaczyna się w sytuacji \(\displaystyle{ ( 2n + 2m - 4)}\). Prawdopodobnie chodzi o to, że rozpatrujemy każdą krawędź (\(\displaystyle{ 2n}\) i \(\displaystyle{ 2m}\)) i odejmujemy cztery rogi, czyli wykluczamy pierwszą sytuację, gdy król stał w rogu.

W sytaucji gdy król może być wewnątrz szachownicy wykluczając przypadki rogów i krawędzi też jest mało "klarowny". \(\displaystyle{ (mn - 9)}\), tutaj rozumiem, że wokół króla stojącego wewnątrz szachownicy jest \(\displaystyle{ 8}\) pól i do tego uwzględniamy samego króla. Zapis \(\displaystyle{ n cdot m - 2 cdot m - 2 cdot n}\) oznacza po prostu, że od wszystkich pól szachownicy odejmujemy jej krawędzie?
Awatar użytkownika
kerajs
Użytkownik
Użytkownik
Posty: 8570
Rejestracja: 17 maja 2013, o 10:23
Płeć: Mężczyzna
Podziękował: 306 razy
Pomógł: 3347 razy

Dwa króle na szachownicy

Post autor: kerajs »

1) Zauważ że przyjmujesz szachownice w których \(\displaystyle{ n,m \in \left\{ 3,4,5,6,7,...\right\}}\), i tylko dla takich szachownic problematyczne wzory mają (po ich poprawieniu) sens.
Sadzę, że należałoby także rozważyć dziwne szachownice, w których jeden z boków wynosi 1 lub 2.

2.
Nie rozumiem dlaczego ignorujesz post Chromosoma który poprawia wzory myszki9 .

3.
FaloZ pisze:Sytuacja, gdy król stoi w rogu jest dla mnie jasna, bo szachownica jest wymiaru \(\displaystyle{ n \times m}\) i eliminujemy trzy pola oraz miejsce, na którym stoi król. Dla jednego rogu mamy zatem \(\displaystyle{ (mn-4)}\). Wynik mnożymy czterokrotnie z racji, iż szachownica posiada dokładnie \(\displaystyle{ 4}\) rogi.
Takie podejście wymusza przyjęcie nienapisanego założenia, iż króle są rozróżnialne. Wynika to z dublowania zliczanych wyników. Np: zdarzenie gdy jeden król stoi w narożniku (1,1) a drugi w rogu (1,n) jest zliczane ponownie gdy jeden król stoi w narożniku (1,n) a drugi w (1,1). Tak tez jest w kolejnych rozważanych przypadkach ustawień króli.
A co gdy mamy dwa czarne króle?

4.
FaloZ pisze: Problem zaczyna się dalej. Sytuacja, kiedy król stoi przy krawędzi szachownicy jest prawie jasna. Przypadek \(\displaystyle{ (mn-6)}\) jest klarowny, bo mamy tutaj podobną sytuację jak w przypadku, gdy król stoi w rogu. Problem zaczyna się w sytuacji \(\displaystyle{ ( 2n + 2m - 4)}\). Prawdopodobnie chodzi o to, że rozpatrujemy każdą krawędź (\(\displaystyle{ 2n}\) i \(\displaystyle{ 2m}\)) i odejmujemy cztery rogi, czyli wykluczamy pierwszą sytuację, gdy król stał w rogu.
Pól które są polami skrajnymi, ale nie rogami, jest:
\(\displaystyle{ (n-2)+(m-2)+(n-2)+(m-2)=2n+2m-8}\)

5.
FaloZ pisze: W sytaucji gdy król może być wewnątrz szachownicy wykluczając przypadki rogów i krawędzi też jest mało "klarowny". \(\displaystyle{ (mn - 9)}\), tutaj rozumiem, że wokół króla stojącego wewnątrz szachownicy jest \(\displaystyle{ 8}\) pól i do tego uwzględniamy samego króla. Zapis \(\displaystyle{ n \cdot m - 2 \cdot m - 2 \cdot n}\) oznacza po prostu, że od wszystkich pól szachownicy odejmujemy jej krawędzie?
Miało to oznaczać, lecz rogi zostały odjęte dwukrotnie. Powinno być \(\displaystyle{ mn-2n-2(m-2)}\) albo \(\displaystyle{ (n-2)(m-2)}\)

6.
Ja rozwiązywałbym inaczej. Od wszystkich możliwych ustawień odejmowałbym ustawienia gdy króle stoją na sąsiednich polach.
Ponadto rozważałbym dwa przypadki: dla rozróżnialnych i nierozróżnialnych króli.
ODPOWIEDZ