III MEMO - Zadanie 8

Zawody matematyczne:

III MEMO, 2009

Każde z pól szachownicy o wymiarach $2009\times 2009$ kolorujemy jednym z $n$ kolorów (nie każdy kolor musi być wykorzystany). Mówimy, że kolor jest spójny, jeżeli dla dowolnych dwóch pól tego koloru można za pomocą ciągu ruchów przeprowadzić hetmana z jednego pola na drugie, stawiając go jedynie na polach w tym kolorze. W szczególności, jeśli pewnym kolorem pomalowano tylko jedno pole, to również jest on spójny. Wyznaczyć największą liczbę $n$ , dla której przy dowolnym kolorowaniu szachownicy co najmniej jeden z kolorów jest spójny.

Uwaga: Ruch hetmanem polega na przesunięciu go o dowolną liczbę pól w pionie, poziomie lub po skosie.

Rozwiązanie

Udowodnimy, że największe takie $n$ wynosi 2. Na początku wskażemy kolorowanie planszy trzema kolorami, dla którego żaden kolor nie jest spójny.

Na rysunku przedsawiono kolorowanie częściowe planszy $11\times 11$ . Widzimy, że duże O w danym kolorze nie jest połączone z żadnym małym o w tym kolorze. (Mówimy, że pola $a$ i $b$ są połączone, jeśli hetman może przejść z $a$ na $b$ w serii ruchów zgodnych z warunkami zadania.) Kolorowanie pozostałych pól jest nieistotne.

Analogicznie możemy pomalować każdą planszę $k\times k$ dla $k\geq6$ . Przypisujemy polom współrzędne $(i,j)$ , gdzie $i,j\in\{1,\dots,n\}$ . Malujemy $(2,1)$ na czerwono, $(1,2)$ na niebiesko, $(1,1),(2,2),(2,3),(3,2)$ i $(k,4)$ na czarno. W przypadku pozostałych pól kolejne etapy kolorowania są następujące: Wszystkie pola leżące na jednej linii (pionowej, poziomej lub ukośnej), zawierające $(2,1)$ , malujemy na niebiesko. Następnie nie pomalowane jeszcze pola na liniach zawierających $(1,2)$ lub $(k,4)$ dostają kolor czerwony. Pozostałe pola malujemy dowolnie. Jeżeli $n\geq6$ , pola $(2,1)$ , $(1,2)$ i $(k,4)$ nie są połączone z żadnym innym polem w odpowiadającym im kolorze.

Udowodnimy teraz, że dla $k,m\geq1$ i dowolnego czerwono-niebieskiego kolorowania szachownicy $k\times m$ , przynajmniej jeden kolor jest spójny. Postępujemy indukcyjnie ze względu na $k+m$ .

Oczywiście gdy $k+m=2$ teza jest spełniona. Ustalmy $n,m\geq1$ i załóżmy, że teza jest prawdziwa dla dowolnej szachownicy $k'\times m'$ , gdzie $k'+m'<n+m$ . Rozważmy dowolne kolorowanie planszy $S$ o wymiarach $k\times m$ . Oznaczmy przez $S_1$ , $S_2$ , $S_3$ plansze otrzymane z $S$ przez usunięcie odpowiednio: pierwszej kolumny, ostatniej kolumny, ostatniego wiersza. Na mocy założenia indukcyjnego i zasady szufladkowej, istnieją dwie plansze, $S_i$ , $S_j$ , na których jeden z kolorów jest spójny. Możemy przyjąć, że jest to kolor czerwony. Niech $A_0=S_i\cap S_j$ , $A_1=S_j\setminus S_i$ i $A_2=S_i\setminus S_j$ .

Oto kilka łatwych do sprawdzenia obserwacji:

Kolor jest spójny wtedy i tylko wtedy, gdy każde dwa pola w tym kolorze są połączone.

Dla dowolnych pól $a$ , $b$ , $c$ , jeżeli $a$ jest połączone z $b$ , a $b$ jest połączone z $c$ , to $a$ jest połączone z $c$ .

Jeśli plansza $A_0$ jest monochromatyczna (tzn. wszystkie jej pola są tego samego koloru),

i jest niebieska, to niebieski jest kolorem spójnym na całej planszy $S$ . Wynika to z poprzedniej obserwacji i z faktu, że $A_0$ jest planszą $(k-1)\times(m-1)$ lub $(k-2)\times m$ , a w obu przypadkach każde niebieskie pole na brzegu $S$ leży w jednej linii z jakimś niebieskim polem z $A_0$ .

Jeżeli istnieje czerwone pole na $A_0$ , to czerwony jest kolorem spójnym na $S_i\cup S_j$ . Twierdzimy to na mocy poprzednich trzech obserwacji i faktu, że czerwony jest spójny zarówno na $S_i$ , jaki i na $S_j$ .

Jeżeli plansze $A_1$ i $A_2$ są monochromatyczne, powiedzmy niebieskie, to niebieski jest spójny na całej planszy $S$ . Rzeczywiście, każde niebieskie pole z $S$ leży w jednej linii z jakimś niebieskim polem z $A_1$ lub $A_2$ .

Przypuśćmy nie wprost, że ani niebieski, ani czerwony nie jest kolorem spójnym na $S$ . Wtedy, na mocy (3), plansza $A_0$ musi mieć jakieś pole czerwone. Zauważmy, że $S_i\cup S_j$ pokrywa albo całą szachownicę $S$ , albo prawie całą, z wyjątkiem jednego rogu.

W pierwszym przypadku z obserwacji (4) wynika, że czerwony jest spójny na $S$ , dochodzimy więc do sprzeczności.

W drugim przypadku jest tylko jedna możliwość znalezienia dwóch niepołączonych czerwonych pól na $S$ : róg szachownicy $c$ niepokryty przez $S_i\cup S_j$ musi być czerwony i żadne pole na liniach zawierających $c$ nie może być czerwone. Ale wtedy mamy do czynienia z sytuacją z obserwacji (5), zatem niebieski jest kolorem spójnym na $S$ . Ponownie doszliśmy do sprzeczności.

Tym samym udowodniliśmy tezę indukcyjną dla szachownicy $k\times m$ .

Uwaga: Oto alternatywna konstrukcja kolorowania szachownicy $2009\times 2009$ trzema kolorami. Ponumerujmy je 1, 2, 3, z których każdy jest niespójny: Na początku w każde z $2009^2$ pól wpisujemy liczbę 0. W polu $(2,2009)$ dodajemy 1, a w polu $(3,1)$ dodajemy 2. Teraz w każdym polu osiągalnym jednym ruchem hetmana z $(2,2009)$ dodajemy 2, przy czym nie zmieniamy liczby 1 w polu $(2,2009)$ . W każdym polu osiągalnym jednym ruchem hetmana z $(3,1)$ dodajemy 1, ale nie zmieniamy liczby 2 w polu $(3,1)$ . Zauważmy, że pola $(2,2009)$ i $(3,1)$ mają inne kolory szachowe (czarny i biały), więc goniec, startując z $(2,2009)$ , porusza się po polach innego koloru niż goniec ustawiony na $(3,1)$ . Ponadto goniec z $(2,2009)$ nie ma w zasięgu rażenia pól pierwszego wiersza, zaś w zasięgu gońca z $(3,1)$ nie leżą pola z wiersza 2009. Dlatego liczba $1+2=3$ znajduje się tylko w czterech polach: $(2,1)$ , $(2,2)$ , $(3,2009)$ , $(3,2009-1)$ . Dwa pierwsze pola nie są połączone z dwoma następnymi. Dodajemy teraz dowolnie 1 lub 2 we wszystkich polach, w których nadal jest liczba 0. Zauważmy, że żadne z nich nie jest połączone ani z polem $(2,2009)$ (z numerem 1), ani z $(3,1)$ (z liczbą 2). Zatem wszystkie kolory: 1, 2, 3, są niespójne.