LI OM - III - Zadanie 5

Dla danej liczby naturalnej $ n \geq 2 $ znaleźć najmniejszą liczbę $ k $ o następującej własności. Z dowolnego $ k $-elementowego zbioru pól szachownicy $ n \times n $, można wybrać taki niepusty podzbiór, że liczba pól tego podzbioru w każdym wierszu i w każdej kolumnie szachownicy jest parzysta.

Rozwiązanie

Udowodnimy następujące dwa zdania:

  1. Z dowolnego zbioru złożonego z $ m + n $ pól szachownicy o wymiarach $ m \times n $ ($ m,n \geq 2 $) można wybrać niepusty podzbiór mający w każdym wierszu i w każdej kolumnie szachownicy parzystą liczbę pól.

  2. Istnieje zbiór $ m+n-1 $ pól szachownicy o wymiarach $ m \times n $, z którego nie da się wybrać niepustego podzbioru mającego w każdym wierszu i w każdej kolumnie szachownicy parzystą liczbę pól.

Z powyższych zdań zastosowanych dla $ m = n $ wnioskujemy, że najmniejszą liczbą spełniającą warunki zadania jest $ k = 2n $.

Dowód zdania 1.

Przeprowadzimy dowód indukcyjny względem $ m + n $. Dla $ m = 2 $, $ n = 2 $ teza zdania 1 jest prawdziwa.

Ustalmy dwie liczby naturalne $ m $, $ n $ o sumie większej niż $ 4 $ i załóżmy, że zdanie $ 1 $ jest prawdziwe dla dowolnej szachownicy o sumie wymiarów mniejszej niż $ m + n $. Rozważmy dowolny zbiór A złożony z $ m + n $ pól szachownicy $ S $ o wymiarach $ m \times n $. Możliwe są następujące trzy przypadki:

  1. istnieje wiersz lub kolumna szachownicy $ S $ nie zawierająca żadnego pola ze zbioru $ A $;
  2. istnieje wiersz lub kolumna szachownicy $ S $, w której znajduje się dokładnie jedno pole ze zbioru $ A $;
  3. w każdym wierszu i w każdej kolumnie znajdują się co najmniej dwa pola ze zbioru $ A $.

om51_3r_img_4.jpg

W przypadku (a) usuwamy z szachownicy $ S $ tę kolumnę (lub wiersz), która nie zawiera żadnego pola ze zbioru $ A $. Następnie usuwamy ze zbioru $ A $ dowolne pole (na rysunku 1 pola zbioru A oznaczone są kółeczkami). W ten sposób otrzymujemy nową szachownicę, która zawiera pewien zbiór $ A' $ złożony z $ m + n - 1 $ pól i której suma wymiarów jest równa $ m + n - 1 $ (rys. 2). Stąd wynika, że każdy z wymiarów uzyskanej szachownicy jest nie mniejszy niż $ 2 $. Zatem na mocy założenia indukcyjnego można wybrać ze zbioru $ A' $ niepusty podzbiór mający w każdym wierszu i w każdej kolumnie parzystą liczbę pól. Wklejając z powrotem usuniętą kolumnę lub usunięty wiersz na swoje miejsce (rys. 3) otrzymujemy żądany podzbiór zbioru $ A $.

om51_3r_img_5.jpg

Podobnie postępujemy w przypadku (b): znajdujemy najpierw kolumnę (lub wiersz), w której znajduje się dokładnie jedno pole ze zbioru $ A $, a następnie usuwamy tę kolumnę z szachownicy $ S $ (rys. 4). W rezultacie otrzymujemy nową szachownicę, która zawiera pewien zbiór $ A $' złożony z $ m + n - 1 $ pól i której suma wymiarów jest równa $ m + n - 1 $ (rys. 5). Tak jak wyżej, stosujemy założenie indukcyjne, po czym wklejamy z powrotem usuniętą kolumnę lub usunięty wiersz (rys. 6).

Rozpatrzmy przypadek (c). Niech $ k_1,k_2,\ldots,k_n, w_1,w_2,\ldots,w_m $ oznaczają odpowiednio liczby pól zbioru $ A $ w poszczególnych kolumnach i wierszach. Wówczas

\[<br /> (k_1 + k_2 +\ldots + k_n) + (w_1 + w_2 +\ldots + w_m) = 2(m + n).<br /> \]

Ponadto $ k_i,w_j \geq 2 $ dla wszystkich $ i $, $ j $. Stąd wynika, że $ k_i = w_j = 2 $. Zatem zbiór $ A $ ma w każdej kolumnie i w każdym wierszu dokładnie dwa pola. To oznacza, że liczba pól zbioru $ A $ w każdym wierszu i w każdej kolumnie jest parzysta.

Dowód indukcyjny, a tym samym dowód zdania 1, został zakończony.

Dowód zdania 2.

om51_3r_img_6.jpg

Rozważmy zbiór $ A $ złożony ze wszystkich $ m + n- 1 $ pól szachownicy o wymiarach $ m \times n $ znajdujących się w dolnym wierszu i pierwszej kolumnie (rys. 7). Aby otrzymać parzystą liczbę pól w kolumnach od drugiej do ostatniej musimy usunąć ze zbioru $ A $ pola, które się w tych kolumnach znajdują. Po ich usunięciu widzimy, że z tego samego powodu musimy usunąć pozostałe pola zbioru $ A $. To kończy dowód zdania $ 2 $.

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

Komentarze

Dodaj nową odpowiedź