LI OM - III - Zadanie 5

Zawody matematyczne:

LI OM, 1999-2000

Etap:

III

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:

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

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

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

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.

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