XXXVIII OM - II - Zadanie 3

Na szachownicy o wymiarach 1000 na 1000 i polach pokolorowanych w zwykły sposób na biało i czarno jest dany zbiór A złożony z 1000 pól. Każde dwa pola zbioru A można połączyć ciągiem pól zbioru A tak, by kolejne pola miały wspólny bok. Dowieść, że w zbiorze A jest co najmniej 250 pól białych.

Rozwiązanie

Skończony ciąg pól szachownicy (o dowolnych wymiarach) mający tę i własność, że każde dwa kolejne pola mają wspólny bok, będziemy nazywali drogą, a liczbę pól w tym ciągu zmniejszoną o $ 1 $ - długością drogi (pojedyncze pole stanowi drogę długości $ 0 $).

Niepusty zbiór $ A $ złożony z dowolnej liczby pól szachownicy i taki, że każde jego dwa pola łączy droga w nim zawarta, będziemy nazywali spójnym.

Udowodnimy przez indukcję względem $ n $, że liczba białych pól w dowolnym spójnym zbiorze $ A $ złożonym z $ n $ pól jest nie mniejsza niż $ (n-1)/4 $. Dla $ n = 1000 $ wyniknie stąd teza zadania.

Gdy $ n = 1 $, podana wartość wynosi $ 0 $, więc nie ma czego dowodzić.

Ustalmy liczbę naturalną $ n > 1 $ i załóżmy, że każdy $ m $-polowy zbiór spójny, gdzie $ m $ jest dowolną liczbą mniejszą od n, ma co najmniej $ (m-1)/4 $ pól białych. Niech będzie dany zbiór spójny $ A $ złożony z $ n $ pól i niech $ b $ będzie liczbą białych pól zbioru $ A $. Mamy dowieść, że

\[<br />
(1) \qquad 4b \geq n-1.<br />
\]

Jeśli to wykażemy, dowód naszego stwierdzenia będzie zakończony, na mocy zasady indukcji.

Nierówność (1) udowodnimy dwoma sposobami.

Wybierzmy ze zbioru $ A $ jedno pole białe (jego istnienie wynika z tego, że $ n > 1 $),
nazwijmy je $ P $ i usuńmy je ze zbioru $ A $. Otrzymany zbiór $ n-1 $ pól oznaczmy przez $ A' $. Jeśli $ Q $ jest dowolnie ustalonym polem w $ A' $, to zbiór wszystkich pól zbioru $ A' $, które dadzą się połączyć z $ Q $ drogą zawartą w $ A' $, jest spójny. Ponieważ każde pole zbioru $ A $ łączy z polem $ P $ droga zawarta w $ A $, która musi przechodzić przez jedno z czterech pól sąsiadujących z $ P $, przeto każde pole zbioru $ A' $ łączy z jednym z tych czterech pól droga zawarta w $ A' $.

Wynika stąd, że $ A' $ jest sumą co najwyżej czterech niepustych rozłącznych zbiorów spójnych. Nazwijmy je $ A_1,\ldots, A_k $ ($ 1 \leq k \leq 4 $) i przyjmijmy, że zbiór $ A_j $ składa się z $ m_j $ pól, w tym $ b_j $ białych ($ j = 1, \ldots,k $).

Oczywiście

\[<br />
\sum_{j=1}^km_j=n-1, \quad \sum_{j=1}^k b_j=b-1<br />
\]

(bo pole P jest białe). Z założenia indukcyjnego

\[<br />
4b_j \geq m_j -1 \quad \textrm{dla } q= 1, \ldots, k.<br />
\]

Wystarczy dodać stronami te nierówności, by otrzymać

\[<br />
4(b-1) \geq n-1-k.<br />
\]

Dowodzona nierówność (1) natychmiast stąd wynika, bo $ k \leq 4 $.

Komentarze

Dodaj nową odpowiedź