LX OM - I - Zadanie 1

Na niektórych polach szachownicy rozmiaru $ m\times n $ ustawiono wieże.
Wiadomo, że dowolna wieża znajduje się w polu rażenia co najwyżej
dwóch innych wież.

Wyznaczyć, w zależności od $ m, n \geq 2 $, największą liczbę wież na szachownicy,
dla której taka sytuacja jest możliwa.

Rozwiązanie

Odpowiedź: $ m+n $ wież.

Udowodnimy najpierw, że na prostokątnej szachownicy $ m\times n $ $ (m, n \geqslant 1) $ można ustawić
najwyżej $ m+n $ wież tak, by każda wieża znajdowała się w polu rażenia nie więcej niż dwóch innych.
Dowód przeprowadzimy na trzy sposoby.

Sposób I

Nazwijmy wiersz związanym, jeżeli w wierszu tym ustawiona jest wieża $ w $ znajdująca się w polu rażenia
dwóch innych wież stojących w tej samej kolumnie, co wieża $ w $. Analogicznie kolumną związaną nazywamy kolumnę,
która zawiera wieżę będącą w polu rażenia dwóch wież z tego samego wiersza.

Z warunków zadania wynika, że każda związana linia (wiersz lub kolumna) zawiera dokładnie jedną wieżę.
Niech $ s $ i $ t $ oznaczają odpowiednio liczbę wierszy i kolumn związanych. Wówczas liczba wszystkich wież
znajdujących się w związanych liniach nie przekracza $ s+t $.

Z drugiej strony, weźmy pod uwagę zbiór pól szachownicy nie znajdujących się w żadnej związanej linii.
Pola takie nazwijmy niezwiązanymi. Z określenia kolumn związanych wynika, że w każdym wierszu najwyżej dwie
wieże rozmieszczone są na polach niezwiązanych — mogą to bowiem być tylko „skrajne” wieże stojące w tym wierszu.
Ponadto wszystkie pola niezwiązane zawarte są w $ m - s $ niezwiązanych wierszach. Zatem liczba wież znajdujących
się na niezwiązanych polach jest nie większa niż $ 2(m - s) $. Podobnie uzasadniamy, że liczba tych wież nie
przekracza $ 2(n -t) $.

Korzystając z nierówności $ 2\cdot\min\{x,y\}\leq x+y $ stwierdzamy ostatecznie, że liczba wszystkich
wież na szachownicy jest nie większa niż

\[<br /> s+t+2\cdot\min\{m-s,n-t\}\leq s+ t+(m -s)+(n-t)= m+n.<br /> \]

Sposób II

Weźmy pod uwagę odcinki brzegowe, czyli boki pól danej szachownicy zawarte w jej brzegu.
Liczba odcinków brzegowych jest równa $ 2(m+n) $.

Wieża stojąca na szachownicy wyznacza cztery odcinki brzegowe: dwa na górnym i dolnym końcu zajętej
przez nią kolumny oraz dwa na lewym i prawym końcu zajętego przez nią wiersza. Odcinek brzegowy wyznaczony
przez wieżę znajduje się w polu rażenia tej wieży, jeżeli w linii (pionowej bądź poziomej) pomiędzy
wieżą a odcinkiem nie znajduje się żadna inna wieża.

Odcinek brzegowy wyznacza jednoznacznie linię (wiersz albo kolumnę), w którym musi stać wieża mająca
ten odcinek w polu rażenia. Jeżeli w linii tej stoją przynajmniej dwie wieże, dany odcinek znajduje się
w polu rażenia tylko jednej z nich, a mianowicie wieży najbliższej odcinkowi. Każdy odcinek brzegowy
szachownicy znajduje się więc w polu rażenia najwyżej jednej wieży.

Z drugiej strony, zgodnie z warunkami zadania każda wieża znajduje się w polu rażenia najwyżej
dwóch innych wież. Oznacza to, że w polu rażenia dowolnej wieży znajdują się przynajmniej dwa odcinki
brzegowe. Jak wykazaliśmy wcześniej, odcinki znajdujące się w polu rażenia różnych wież są różne.
Ponieważ zaś liczba odcinków brzegowych wynosi $ 2(m+n) $, liczba wież na szachownicy nie może przekraczać $ m+n $.

Sposób III

Tym razem zastosujemy indukcję ze względu na wielkość sumy $ m+n $.

Jeżeli przynajmniej jedna z liczb $ m, n $ jest równa 1, to rozpatrywana teza jest prawdziwa,
gdyż liczba wszystkich pól szachownicy wynosi wówczas $ m+n-1 $ i tym bardziej liczba wież nie może
przekraczać $ m+n-1 $.

Weźmy teraz pod uwagę szachownicę rozmiaru $ m \times n $ (gdzie $ m, n \geq 2 $) z $ t $ wieżami
rozmieszczonymi zgodnie z warunkami zadania.

Przypuśćmy najpierw, że w pewnym wierszu znajdują się przynajmniej trzy wieże. W wierszu tym znajdują
się zatem dwie wieże skrajne oraz co najmniej jedna wieża środkowa. Niech w oznacza jedną
z wież środkowych. Wieża $ w $ znajduje się wówczas w polu rażenia dwóch wież stojących w
tym samym wierszu, co oznacza, że w kolumnie $ K $ zajętej przez wieżę w nie mogą stać żadne inne wieże.
Wykreślając z szachownicy kolumnę $ K $ otrzymujemy szachownicę rozmiaru $ m\times (n-1) $ z $ t-1 $ wieżami
spełniającymi dany w treści zadania warunek. Na mocy założenia indukcyjnego mamy więc

\[<br /> t-1 \leq m+(n-1) = m+n-1.<br /> \]

To daje $ t \leq m+n $, a więc uzyskaliśmy tezę indukcyjną. Podobne rozumowanie przeprowadzamy, gdy istnieje kolumna zawierająca przynajmniej trzy wieże. Pozostaje do rozpatrzenia przypadek, gdy w każdym wierszu i w każdej kolumnie znajdują się najwyżej dwie wieże. Wtedy jednak łączna ich liczba
nie przekracza $ 2\cdot\min\{m,n\}\leq m+n $.

Zakończenie

By zakończyć rozwiązanie, należy jeszcze wskazać żądane rozmieszczenie m+n wież na szachownicy rozmiaru
$ m\times n $, gdzie $ m, n\geq 2 $. Można je uzyskać stawiając wieże na lewym i górnym brzegu szachownicy
oraz w prawym dolnym rogu (rys. 1).

om60_1r_img_1.jpg

Komentarze

Dodaj nową odpowiedź