XXXVIII OM - II - Zadanie 3

Zawody matematyczne:

XXXVIII OM, 1986-1987

Etap:

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

$ (1) \qquad 4b \geq n-1. $

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