LX OM - I - Zadanie 1

Zawody matematyczne:

LX OM, 2008-2009

Etap:

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