Na każdym polu szachownicy \(\displaystyle{ m \times k}\) jest jeden pionek. Należy przemieścić pionki w taki sposób aby każdy z nich miał tylko jednego sąsiada (z początkowego ustawienia).
Przez sąsiednie piony rozumie się takie, które stały na polach sąsiednich (tj. mających wspólny bok).
Dla jakich \(\displaystyle{ m, k}\) jest to możliwym ?
Zamiana pionków
-
mol_ksiazkowy
- Użytkownik
- Posty: 11406
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3155 razy
- Pomógł: 748 razy
-
kerajs
- Użytkownik
- Posty: 8585
- Rejestracja: 17 maja 2013, o 10:23
- Płeć: Mężczyzna
- Podziękował: 307 razy
- Pomógł: 3351 razy
Re: Zamiana pionków
1)
Gdy \(\displaystyle{ m}\) i \(\displaystyle{ k}\) będą liczbami nieparzystymi to na szachownicy będzie nieparzysta liczba pionów. Dowolnemu pionowi przypisuję jednego z sąsiadów, z którym po przemieszczeniu pionów nadal będzie sąsiadował. Przypisywanie przeprowadzam dla pozostałych niesparowanych pionów. Żaden z nich nie może wybrać sąsiada już sparowanego, gdyż ten po przemieszczeniu pionów miałby za sąsiada więcej niż jednego z sąsiadów sprzed przemieszczenia. Nawet przy optymalnym dobraniu pionów w sąsiadujące pary zostanie jeden któremu sąsiada nie można przypisać.
Wniosek: \(\displaystyle{ m}\) i \(\displaystyle{ k}\) nie mogą być liczbami nieparzystymi.
2)
Gdy jedna z liczb \(\displaystyle{ m,k}\) jest parzysta to pełne sparowanie z 1) jest możliwe.
Pozostaje wskazać taki przykładowy podział i przemieszczenie pionów w tym podziale, aby warunek z treści zadania był spełniony.
Niech \(\displaystyle{ m}\) będzie parzysta. Łączę w pary piony o współrzędnych: \(\displaystyle{ (1,j)}\) i \(\displaystyle{ (2, j)}\) , \(\displaystyle{ (3,j)}\) i \(\displaystyle{ (4, j)}\) , ... , \(\displaystyle{ (m-1,j)}\) i \(\displaystyle{ (m, j)}\); a prostokątne pola na których stoją pary stworzą, po uprzednim pomalowaniu, szachownicę z prostokątnymi polami. Przemieszczenie spełniające warunki zadania dostanie się przez przestawienie pionów na każdym z prostokątnych pól w tym samym kolorze.
Odp: Przestawienie jest możliwe jeśli przynajmniej jeden bok pierwotnej szachownicy będzie miał parzystą liczbę pól.
PS
Gdyby w zadaniu był dodatkowy warunek, że po przemieszczeniu żaden z pionów nie stoi na swoim miejscu, to do przestawienia z 2) wystarczy dodać symetrię własną środkową lub osiową szachownicy.
Gdy \(\displaystyle{ m}\) i \(\displaystyle{ k}\) będą liczbami nieparzystymi to na szachownicy będzie nieparzysta liczba pionów. Dowolnemu pionowi przypisuję jednego z sąsiadów, z którym po przemieszczeniu pionów nadal będzie sąsiadował. Przypisywanie przeprowadzam dla pozostałych niesparowanych pionów. Żaden z nich nie może wybrać sąsiada już sparowanego, gdyż ten po przemieszczeniu pionów miałby za sąsiada więcej niż jednego z sąsiadów sprzed przemieszczenia. Nawet przy optymalnym dobraniu pionów w sąsiadujące pary zostanie jeden któremu sąsiada nie można przypisać.
Wniosek: \(\displaystyle{ m}\) i \(\displaystyle{ k}\) nie mogą być liczbami nieparzystymi.
2)
Gdy jedna z liczb \(\displaystyle{ m,k}\) jest parzysta to pełne sparowanie z 1) jest możliwe.
Pozostaje wskazać taki przykładowy podział i przemieszczenie pionów w tym podziale, aby warunek z treści zadania był spełniony.
Niech \(\displaystyle{ m}\) będzie parzysta. Łączę w pary piony o współrzędnych: \(\displaystyle{ (1,j)}\) i \(\displaystyle{ (2, j)}\) , \(\displaystyle{ (3,j)}\) i \(\displaystyle{ (4, j)}\) , ... , \(\displaystyle{ (m-1,j)}\) i \(\displaystyle{ (m, j)}\); a prostokątne pola na których stoją pary stworzą, po uprzednim pomalowaniu, szachownicę z prostokątnymi polami. Przemieszczenie spełniające warunki zadania dostanie się przez przestawienie pionów na każdym z prostokątnych pól w tym samym kolorze.
Odp: Przestawienie jest możliwe jeśli przynajmniej jeden bok pierwotnej szachownicy będzie miał parzystą liczbę pól.
PS
Gdyby w zadaniu był dodatkowy warunek, że po przemieszczeniu żaden z pionów nie stoi na swoim miejscu, to do przestawienia z 2) wystarczy dodać symetrię własną środkową lub osiową szachownicy.