XXXIV - III - Zadanie 3

Rozważamy grę jednoosobową na nieskończonej szachownicy opartą na następującej regule. Jeżeli na dwóch polach mających wspólny bok stoją plony i następne pole jest puste (trzy omawiane pola leżą na jednej linii poziomej lub pionowej), to możemy te piony usunąć i postawić jeden pion na trzecim z tych pól (które było puste).
Udowodnić, że jeżeli w pozycji początkowej piony wypełniają prostokąt o liczbie pól podzielnej przez 3, to nie możemy otrzymać pozycji, w której na szachownicy jest tylko jeden pion.

Rozwiązanie

Wprowadzając na płaszczyźnie odpowiedni układ współrzędnych możemy każdemu polu szachownicy przyporządkować parę liczb całkowitych, przy czym dwóm polom sąsiednim leżącym w jednym wierszu pionowym odpowiadają liczby $ (m, n) $ i $ (m,n+1) $, a dwóm sąsiednim polom leżącym w jednym wierszu poziomym - liczby $ (m, n) $ i $ (m+1, n) $. Każdemu polu szachownicy możemy przyporządkować sumę $ m+n $ jego współrzędnych, a następnie resztę z podzielenia $ m+n $ przez $ 3 $. W ten sposób podzielimy wszystkie pola na trzy zbiory:

\[<br />
\begin{split}<br />
& A_0 = \{(m, n) \colon m+n \equiv 0 \pmod 3\},\\<br />
& A_1 = \{(m, n) \colon m+n \equiv 0 \pmod 3\},\\<br />
& A_2 = \{(m, n) \colon m+n \equiv 0 \pmod 3\},<br />
\end{split}<br />
\]

Piony ustawione w pozycji początkowej zajmują prostokąt o wymiarach $ 3k \times l $ lub $ l \times 3k $. W każdym wierszu równoległym do boku długości $ 3k $ co trzeci pion stoi na polu należącym do $ A_0 $, co trzeci - na polu należącym do $ A_1 $ i co trzeci na polu należącym do $ A_2 $ (sumy współrzędnych kolejnych pól są kolejnymi liczbami całkowitymi). Wobec tego w pozycji początkowej liczby pionów zajmujących pola należące do $ A_0 $, do $ A_1 $ i do $ A_2 $ są równe. Jeśli w pewnej pozycji dokładnie $ a_0 $ pionów zajmuje pola ze zbioru $ A_0 $, $ a_1 $ pionów - pola ze zbioru $ A_1 $, $ a_2 $ pionów - ze zbioru $ A_2 $, że dokonując ruchu dozwolonego w grze zabieramy dwa piony, a dostawiamy trzeci, przy czym zmian tych dokonujemy na trzech polach występujących obok siebie w jednym rzędzie, więc każde z tych pól należy do innego ze zbiorów $ A_0 $, $ A_1 $, $ A_2 $. Zatem dwie z liczb $ a_0 $, $ a_1 $, $ a_2 $ zmniejszają się o $ 1 $, pozostała liczba wzrasta o $ 1 $. Ponieważ w pozycji początkowej liczby pionów zajmujących pola ze zbiorów $ A_0 $, $ A_1 $, $ A_2 $ były równe, więc po każdej serii dozwolonych ruchów liczby pionów zajmujących pola ze zbiorów $ A_0 $, $ A_1 $, $ A_2 $ są liczbami tej samej parzystości. Jeśli na szachownicy jest tylko jeden pion, to należy on do jednego ze zbiorów $ A_1 $ np. do $ A_0 $ i wówczas sytuacji tej odpowiadają liczby $ a_0 = 1 $, $ a_1 = 0 $, $ a_2 = 0 $, które nie są tej samej parzystości. Wynika stąd, że nie można doprowadzić do pozycji, w której na szachownicy pozostałby tylko jeden pion.

Komentarze

Dodaj nową odpowiedź