XXXIV - III - Zadanie 3

Zawody matematyczne:

XXXIV OM, 1982-1983

Etap:

III

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:

$ \begin{split} & A_0 = \{(m, n) \colon m+n \equiv 0 \pmod 3\},\\ & A_1 = \{(m, n) \colon m+n \equiv 0 \pmod 3\},\\ & A_2 = \{(m, n) \colon m+n \equiv 0 \pmod 3\}, \end{split} $

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.