LIX OM - II -Zadanie 4

Zawody matematyczne:

LIX OM, 2007-2008

Etap:

W każdym polu kwadratowej tablicy o rozmiarach $n \times n$ napisana jest liczba całkowita. Możemy wielokrotnie
wykonywać następującą operację: Wybieramy dowolne pole tabeli i zmniejszamy wpisaną weń liczbę o liczbę pól sąsiednich
(mających wspólny bok z wybranym polem), zaś każdą z liczb wpisanych w pola sąsiednie zwiększamy o 1.

Dla każdej liczby całkowitej $n \geqslant 2$ rozstrzygnąć, czy z dowolnej początkowej tabeli, w której suma wszystkich
$n^2$ liczb jest równa zeru, można otrzymać tabelę składającą się z samych zer.

Rozwiązanie

Niech $P$ oznacza przekątną tabeli łączącą jej lewy górny róg z prawym dolnym rogiem. Udowodnimy, że w wyniku
wykonania opisanej operacji nie zmienia się parzystość sumy liczb znajdujących się na przekątnej $P$ (na rys. 2 pola
leżące na przekątnej $P$ są zacieniowane).

Dla każdego pola na przekątnej $P$ liczba pól sąsiednich wynosi 2 albo 4 i żadne z nich nie leży na przekątnej $P$ .
Każde pole sąsiadujące z przekątną $P$ (na rys. 2 takie pola oznaczone są krzyżykami) sąsiaduje z dokładnie dwoma polami
leżącymi na przekątnej $P$ . Pozostałe pola tabeli nie leżą na przekątnej $P$ i z nią nie sąsiadują. Jeżeli więc suma liczb
na przekątnej $P$ przed wykonaniem operacji wynosiła $s$ , to w wyniku jej wykonania suma ta będzie równa $s-4$ , $s-2$ , $s$ lub
$s+2$ , czyli jej parzystość nie zmieni się.

Zatem jeśli na początku wpiszemy do tabeli liczbę 1 w lewym górnym rogu, liczbę -1 w polu leżącym w prawym górnym rogu
oraz liczbę 0 w każde z pozostałych pól, to suma wszystkich liczb w tabeli będzie równa zeru, ale po wykonaniu dowolnej
ilości operacji suma liczb leżących na przekątnej $P$ będzie nieparzysta. Wobec tego nie jest możliwe, by przekątna $P$ ,
a tym bardziej — cała tabela, składała się z samych zer.

Odpowiedź: Dla każdego $n \geqslant 2$ istnieje początkowa tabela o sumie liczb równej zeru, z której nie można
otrzymać tabeli złożonej z samych zer.