/Konkursy/Zadania/Kombinatoryka

Zadanie nr 8671292

Dodaj do ulubionych
Dodaj do rozwiązanych

Na niektórych polach szachownicy rozmiaru m × 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 ≥ 2 , największą liczbę wież na szachownicy, dla której taka sytuacja jest możliwa.

Rozwiązanie

Oczywiście zaczynamy od prób i po jakimś czasie można wymyślić, że da się ustawić m + n wież. Przykład takiego ustawienia na rysunku.

PIC

Spróbujemy pokazać, że więcej wież postawić się nie da.

Sposób I

Przypuśćmy, że na szachownicy da się ustawić m + n + 1 wież tak, aby każda znajdowała się w polu rażenia co najwyżej dwóch. Dodatkowo przyjmijmy, że m ≥ n i m jest liczbą wierszy. Gdyby w każdej kolumnie były co najwyżej 2 wieże to wszystich wież byłoby co najwyżej 2n ≤ m + n < m + n+ 1 . Zatem w pewnej kolumnie muszą być co najmniej 3 wieże.

PIC

Spośród tych wież wybierzmy środkową – jest ona atakowana przez dwie wieże, zatem odpowiadający jej wiersz nie może zawierać żadnych innych wież. Usuwamy ten wiersz i mamy poprawną sytuację w tablicy rozmiaru (m − 1)× n i w której jest m + n = (m − 1 )+ n + 1 wież. To jest nasz krok indukcyjny. Kontynuujemy tę operację aż dojdziemy do tablicy 2 × 2 , na której jest

2 + 2 + 1 = 5

wież. Oczywiście jest to niemożliwe.

Sposób II

Zauważmy, że z warunków zadania wynika, że każda wieża „widzi" co najmniej dwie krawędzie brzegowych pól szachownicy (bo najwyżej dwa ma zasłonięte). Wszystkich takich krawędzi pól jest 2m + 2n , zatem wszystkich wież nie może być więcej niż m + n (bo każde pole brzegowe może widzeć tylko jedna wieża).  
Odpowiedź: m + n

Wersja PDF