III MEMO - Zadanie 8

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.

memo3_r_img_1.jpg

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

memo3_r_img_2.jpg
memo3_r_img_3.jpg

Oto kilka łatwych do sprawdzenia obserwacji:

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

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

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

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

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

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

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

Komentarze

Dodaj nową odpowiedź