LI OM - II - Zadanie 3

Zawody matematyczne:

LI OM, 1999-2000

Etap:

Na polach szachownicy $n \times n$ rozmieszczono $n^2$ różnych liczb całkowitych, po jednej na każdym polu. W każdej kolumnie pole z największą liczbą pomalowano na czerwono. Zbiór $n$ pól szachownicy nazwiemy dopuszczalnym, jeżeli żadne dwa z tych pól nie znajdują się w tym samym wierszu, ani w tej samej kolumnie. Spośród wszystkich zbiorów dopuszczalnych wybrano zbiór, dla którego suma liczb umieszczonych na jego polach jest największa.

Wykazać, że w tak wybranym zbiorze jest czerwone pole.

Rozwiązanie

Przeprowadzimy dowód nie wprost.

Załóżmy, że w wybranym zbiorze dopuszczalnym (oznaczmy go przez $A$ ) nie ma czerwonego pola.

Zdefiniujemy ciąg pól $D_1,E_1,D_2,E_2,\ldots$ danej szachownicy według niżej opisanej reguły. (Dla $n = 8$ proces wyboru pól $D_1,E_1,D_2,E_2,\ldots$ jest przedstawiony na rysunkach 1 i 2. Pola czerwone są zacieniowane, zaś pola ze zbioru $A$ są oznaczone kółkiem.)

Pole $D_1$ jest dowolnym polem ze zbioru $A$ . Niech $E_1$ będzie polem czerwonym leżącym w tej samej kolumnie, co $D_1$ .

Następnie rozważamy to pole $D_2$ ze zbioru $A$ , które leży w tym samym wierszu, co $E_1$ . Przez $E_2$ oznaczamy pole czerwone leżące w tej samej kolumnie, co $D_2$ . Postępowanie to kontynuujemy. (Ogólnie: pole czerwone $E_i$ leży w tej samej kolumnie, co $D_i$ , natomiast pole $D_{i+1}$ jest polem ze zbioru $A$ leżącym w tym samym wierszu, co $E_i$ .)

W ten sposób otrzymujemy ciąg pól $D_1,E_1,D_2,E_2,D_3,\ldots$ , w którym każde pole jednoznacznie wyznacza pole następne. Ponieważ pól czerwonych jest skończenie wiele, więc znajdziemy takie liczby całkowite dodatnie $i$ , $t$ , dla których $E_i = E_{i+t}$ oraz $E_i \neq E_{i+s}$ dla $s= 1, 2, \ldots, t-1$ . (W naszym przykładzie przedstawionym na rysunkach 1 i 2, $E_2 = E_5$ , a więc $i = 2$ , $t = 3$ .)

Usuwamy ze zbioru $A$ pola $D_{i+1},D_{i+2},\ldots,D_{i+t}$ zastępując je odpowiednio polami $E_{i+1},E_{i+2},\ldots,E_{i+t}$ (rys. 3). Otrzymany w ten sposób zbiór oznaczmy przez $B$ .

Z określenia ciągu $D_1,E_1,D_2,E_2,D_3,\ldots$ wynika, że pola

$ D_{i+1},D_{i+2},\ldots,D_{i+t} $

znajdują się odpowiednio w tych samych kolumnach, co pola

$ E_{i+1},E_{i+2},\ldots,E_{i+t} $

oraz odpowiednio w tych samych wierszach, co pola

$ E_i = E_{i+t}, E_{i+1}, E_{i+2}, \ldots, E_{i+t-1} . $

Zatem zbiór $B$ jest dopuszczalny. Ponadto liczby, które zostały napisane na polach $E_{i+1},E_{i+2},\ldots,E_{i+t}$ są większe odpowiednio od liczb napisanych na polach $D_{i+1},D_{i+2},\ldots,D_{i+t}$ . Wynika stąd, że suma liczb napisanych na polach zbioru $B$ jest większa od sumy liczb napisanych na polach zbioru $A$ . To jednak przeczy założeniu, że $A$ ma największą sumę liczb spośród wszystkich zbiorów dopuszczalnych.