LIX OM - II -Zadanie 4

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).

om59_2r_img_3.jpg

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.

  • Wersja do wydrukuWersja do wydruku
  • Podziel się / Zapisz

Komentarze

Dodaj nową odpowiedź