Matematyka.pl

Teza zadania: Dla dowolnego ułożenia wszystkich liczb naturalnych od \(\displaystyle{ 1}\) do \(\displaystyle{ 81}\) w kwadratowej tablicy składającej się \(\displaystyle{ 81}\) jednakowych kwadratowych pól, istnieją dwie sąsiednie różniące się co najmniej o \(\displaystyle{ 6}\).
Dowiedziemy mocniejszej tezy:
Teza wzmocniona: Dla dowolnego ułożenia wszystkich liczb naturalnych od \(\displaystyle{ 1}\) do \(\displaystyle{ 81}\) w kwadratowej tablicy składającej się \(\displaystyle{ 81}\) jednakowych kwadratowych pól, istnieją dwie sąsiednie różniące się co najmniej o \(\displaystyle{ 9}\).
A nawet ją uogólnimy:
Teza uogólniona: Dla każdej liczby naturalnej \(\displaystyle{ n \ge 2}\), dla dowolnego ułożenia wszystkich liczb naturalnych od \(\displaystyle{ 1}\) do \(\displaystyle{ n^{2}}\) w kwadratowej tablicy składającej się \(\displaystyle{ n^{2}}\) jednakowych kwadratowych pól, istnieją dwie sąsiednie różniące się co najmniej o \(\displaystyle{ n}\).
Dowód:
Załóżmy nie wprost, że liczby na dowolnych dwóch polach o wspólnej krawędzi różnią się o mniej niż \(\displaystyle{ n}\). Popatrzmy na zbiory \(\displaystyle{ A_{i}=\left\{ 1, \ 2, \ \ldots, \ i \right\}}\) i \(\displaystyle{ B_{i}=\left\{ i+n, \ i+n+1, \ \ldots, \ \ n^{2}\right\}}\), przy czym z racji przyzwoitości niech \(\displaystyle{ i=1, \ 2, \ \ldots , \ n^{2}-n}\). Oczywiście nie istnieją dwa pola o wspólnej krawędzi z liczbami należącymi do obu tych zbiorów. Załóżmy, że w każdej kolumnie istnieją pola z liczbami i ze zbioru \(\displaystyle{ A_{i}}\) i z \(\displaystyle{ B_{i}}\). Wobec tego w każdej kolumnie musi być choć jedno pól nienależących do tamtych zbiorów (bo jakoś trzeba je rozdzielić), których jest: \(\displaystyle{ \left| \left(A_{i} \cup B_{i}\right)'\right|=n^{2}-\left(i+\left(n^{2}-\left(i+n\right)+1\right)\right)=n-1 <n}\) czyli sprzeczność, bo kolumn jest \(\displaystyle{ n}\). Zatem istnieje kolumna w której są pola z liczbami z tylko jednego zbioru. Analogicznie istnieje wiersz z polami z liczbami z tylko jednego zbioru. Z uwagi na fakt, że każdy wiersz i każda kolumna mają wspólne pole i \(\displaystyle{ A_{i} \cap B_{i} = \emptyset}\) to istnieją wiersz i kolumna z polami z liczbami z tylko jednego z tych zbiorów, który będziemy zwać wyróżnionym. Istnieją i takie konfiguracje w których jest to zbiór \(\displaystyle{ A_{i}}\) (wystarczy położyć \(\displaystyle{ i=n^{2}-n}\)), oraz takie w których jest to zbiór \(\displaystyle{ C_{i}}\) (wystarczy położyć \(\displaystyle{ i=1}\)). Teraz już łatwo, bo skoro istnieją takie naturalne \(\displaystyle{ i}\) dla których wyróżniony jest zbiór \(\displaystyle{ A_{i}}\), to jak to bywa wśród liczb naturalnych istnieje najmniejsze \(\displaystyle{ i}\), dla którego \(\displaystyle{ A_{i}}\) jest wyróżniony. Nie jest to oczywiście \(\displaystyle{ i=1}\). Skoro tak, to \(\displaystyle{ A_{i-1}}\) nie jest zbiorem wyróżnionym, ale dla każdego \(\displaystyle{ i}\) musi istnieć zbiór wyróżniony, więc \(\displaystyle{ B_{i-1}}\) jest zbiorem wyróżnionym. Kolumna w której są pola z liczbami jedynie ze zbioru \(\displaystyle{ A_{i}}\) tnie wiersz z polami w których są liczby jedynie ze zbioru \(\displaystyle{ B_{i-1}}\). Istnieje więc pole z liczbą należącą do \(\displaystyle{ A_{i}}\) i jednocześnie \(\displaystyle{ B_{i-1}}\), ale \(\displaystyle{ A_{i} \cap B_{i-1} = \emptyset}\), bo najmniejsza liczba ze zbioru \(\displaystyle{ B_{i-1}}\) równa \(\displaystyle{ n+i-1}\) jest dla \(\displaystyle{ n \ge 2}\) większa od największej liczby ze zbioru \(\displaystyle{ A_{i}}\) równej \(\displaystyle{ i}\). Otrzymana sprzeczność dowodzi tezy.