Komentarz

LI OM - II - Zadanie 3

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

om51_2r_img_3.jpg
om51_2r_img_4.jpg

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

om51_2r_img_5.jpg

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

\[<br /> D_{i+1},D_{i+2},\ldots,D_{i+t}<br /> \]

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

\[<br /> E_{i+1},E_{i+2},\ldots,E_{i+t}<br /> \]

oraz odpowiednio w tych samych wierszach, co pola

\[<br /> E_i = E_{i+t}, E_{i+1}, E_{i+2}, \ldots, E_{i+t-1} .<br /> \]

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.

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

Dodaj komentarz