Kolorowanie płaszczyzny, prostych i okręgów

O kolorowaniu płaszczyzny raz jeszcze...

Na drugim etapie VIII Olimpiady Matematycznej Gimnazjalistów (obecnie Olimpiady Matematycznej Juniorów) pojawiło się następujące zadanie:

Zadanie. Każdy punkt płaszczyzny należy pomalować na pewien kolor w taki sposób, aby każda prosta była jednokolorowa lub dwukolorowa. Jaka jest największa możliwa liczba kolorów, których można użyć do pomalowania punktów tej płaszczyzny? Odpowiedź uzasadnij.

Odpowiedź brzmi: trzy kolory. Udowodnijmy najpierw nie wprost, że nie możemy użyć czterech kolorów. Załóżmy, że można użyć czterech kolorów - wybierzmy zatem cztery różnokolorowe punkty. Zauważmy, że żadne trzy z nich nie są współliniowe, bo w innym przypadku znaleźlibyśmy trzykolorową prostą. Oznaczmy wybrane przez nas punkty $,,DAB, C$ w taki sposób, by proste $AB$ i $D C$ się przecinały. Ich wspólny punkt oznaczmy jako $|E$ (Rys. 1). Jeśli punkt $|E$ ma taki sam kolor co punkt $|A$ czy $B,$ to prosta $D C$ jest trzykolorowa. W innym przypadku prosta $BA$ jest trzykolorowa. Dowiedliśmy, że kolorując płaszczyznę przy użyciu czterech kolorów, zawsze znajdziemy trzykolorową prostą. Teraz pokażę kolorowanie płaszczyzny trzema kolorami, spełniające warunki zadania. Pokolorujmy całą płaszczyznę jednym kolorem, np. zielonym. Wybierzmy dowolną prostą i pokolorujmy ją innym kolorem, np. niebieskim. Na prostej wybierzmy dowolny punkt i pokolorujmy go trzecim kolorem, np. czerwonym. Wtedy każda prosta jest co najwyżej dwukolorowa (Rys. 2).

Po zawodach zadałam sobie następujące pytanie. Załóżmy, że każda prosta jest co najwyżej trzykolorowa. Jak wiele kolorów mogliśmy wtedy użyć do pokolorowania punktów płaszczyzny? Odpowiedź jest w tym przypadku zaskakująca: mogliśmy użyć nieskończenie wiele kolorów! Pokolorujmy całą płaszczyznę jednym kolorem. Wybierzmy dowolny okrąg i pokolorujmy każdy jego punkt innym kolorem. Jeśli prosta nie ma punktów wspólnych z okręgiem, jest jednokolorowa. Jeśli jest do niego styczna, jest dwukolorowa, a jeśli prosta przecina okrąg, jest trzykolorowa. Możemy postawić analogiczne pytania dla okręgów: na ile kolorów możemy pokolorować punkty płaszczyzny, jeśli każdy okrąg może być co najwyżej dwu- czy trzykolorowy. Rozwiązania tych problemów są bardzo podobne do tych postawionych dla prostych, dlatego znalezienie odpowiedzi pozostawiam Czytelnikowi.

Moja praca odpowiada na jeszcze bardziej złożone pytanie niż to postawione podczas olimpiady: na ile kolorów można pokolorować punkty płaszczyzny, jeśli każda prosta może być co najwyżej $m$ -kolorowa, a każdy okrąg co najwyżej $n$ -kolorowy. W pracy udało mi się znaleźć odpowiedź dla prawie wszystkich wartości $m$ i $n$ - wyjątkiem jest przypadek $m = n = 3$ - umiem pokazać, że w takim przypadku możemy użyć czterech kolorów, ale nie sześciu. W dalszej części artykułu zaprezentuję dowody dotyczące tego problemu. Przypadek pięciu kolorów jest otwarty.

Twierdzenie. Niech $k$ będzie maksymalną liczbą kolorów, na które możemy pokolorować punkty płaszczyzny tak, że każda prosta i każdy okrąg będą co najwyżej trzykolorowe. Wtedy $|4⩽ k ⩽ 6.$

Na początku pokażę kolorowanie płaszczyzny czterema kolorami, takie, że każda prosta i każdy okrąg są co najwyżej trzykolorowe. Pokolorujmy całą płaszczyznę jednym kolorem, np. fioletowym. Wybierzemy okrąg i pokolorujmy go innym kolorem, np. brązowym. Na okręgu wybierzmy dwa punkty i pokolorujmy je na jeszcze inne kolory, np. czerwony i zielony. Wtedy każdy okrąg i każda prosta będą co najwyżej trzykolorowe (Rys. 3). Stąd $|k⩾ 4.$

Załóżmy teraz, że możemy pokolorować płaszczyznę sześcioma kolorami - wybierzmy sześć różnokolorowych punktów. Zauważmy, że możemy znaleźć prostą przechodzącą przez co najmniej dwa punkty, taką że pozostałe wybrane punkty będą leżeć po jednej stronie tej prostej. Z drugiej strony zauważmy, że na takiej prostej mogą leżeć co najwyżej trzy wybrane punkty, bo w innym przypadku znaleźlibyśmy czterokolorową prostą. Rozpatrujemy zatem dwa przypadki ze względu na liczbę wyróżnionych punktów na wybranej prostej. Poniżej przedstawię jeden z nich (rozumowanie dla drugiego z nich jest analogiczne i pozostawiam je Czytelnikowi).

Załóżmy, że na prostej leżą dokładnie dwa wybrane punkty - oznaczmy je jako $|A$ i $B,$ a pozostałe jako $P1,P2,P3,$ i $|P4.$ Spośród kątów $AP1B,AP2B,$ $PA3B$ i $|AP4B$ wybierzmy ten o największej mierze - $|APiB$ (zauważmy, że gdyby były dwa takie kąty, to znaleźlibyśmy czterokolorowy okrąg). Punkt $|P i$ oznaczmy jako $. C$ Spośród pozostałych kątów wybierzmy ten o minimalnej mierze - $AP jB$ (jest tylko jeden taki kąt). Punkt $|P j$ oznaczmy jako $D.$ Pozostałe punkty oznaczmy jako $E$ i $|F.$ Zauważmy, że punkt $|C$ leży wewnątrz okręgu $AEB.$ Rozpatrzmy teraz dwa przypadki:

Punkty $,D C$ i $F$ są współliniowe. Jeden z punktów przecięcia prostej $DF |C$ z okręgiem $AEB$ oznaczam jako $G.$ Jeśli punkt $G$ ma taki sam kolor co któryś z punktów $,D C$ lub $F,$ to okrąg $AEB$ jest czterokolorowy. W innym przypadku prosta $DF C$ jest czterokolorowa (Rys. 4).
Punkty $,D,F C$ nie są współliniowe. Jeden z punktów przecięcia okręgu $DF C$ z okręgiem $AEB$ oznaczam jako $G.$ Jeśli punkt $|G$ ma taki sam kolor co któryś z punktów $,D,F, |C$ to okrąg $AEB$ jest trzykolorowy. W innym przypadku okrąg $DF C$ jest trzykolorowy (Rys. 5).

W każdym przypadku (także dla trzech wybranych punktów na prostej) znajdujemy czterokolorową prostą lub okrąg. Zatem nie możemy wykorzystać sześciu kolorów do pokolorowania punktów płaszczyzny w taki sposób, żeby każda prosta i każdy okrąg były co najwyżej trzykolorowe. Zatem $4 ⩽ k⩽ 6.$ Co ciekawe, w przypadku gdy kolorujemy punkty płaszczyzny z zachowaniem warunku, że każda prosta jest co najwyżej trzykolorowa, a każdy okrąg co najwyżej czterokolorowy, możemy użyć nieskończenie wielu kolorów. Aby to wykazać, potrzebujemy następującego lematu:

Lemat. Istnieje taki zbiór punktów $|𝒳$ o nieskończonej liczbie elementów, że żadne trzy punkty należące do $𝒳$ nie leżą na jednej prostej i żadne cztery nie leżą na jednym okręgu.

Zdefiniujmy przez indukcję ciąg zbiorów $𝒳1,𝒳2, ...,𝒳n,...,$ które spełniają następujące warunki:

$𝒳1 ⊆ 𝒳2 ⊆ ...⊆ 𝒳n ⊆...,$
dla każdego $|n$ żadne trzy punkty należące do zbioru $𝒳n$ nie są współliniowe,
dla każdego $|n$ żadne cztery punkty należące do zbioru $𝒳n$ nie leżą na jednym okręgu,
zbiór $|𝒳n$ zawiera $n + 3$ punkty.

Zbiór $𝒳1$ zawiera wierzchołki dowolnego trójkąta i jego ortocentrum, zatem spełnia wszystkie żądane warunki. Nowy zbiór $𝒳n+1$ ze zbioru $|𝒳n$ tworzymy w następujący sposób: przez każde dwa punkty zbioru $|𝒳n$ prowadzimy prostą, a przez każde trzy okrąg. Niech narysowane obiekty tworzą razem zbiór $|𝒵.$ Zauważmy, że liczba prostych i okręgów jest skończona. Wybierzmy prostą, która nie należy do zbioru $𝒵.$ Proste i okręgi przecinają ją w skończonej liczbie punktów. Wybierzmy zatem punkt $|P,$ który nie leży na żadnej prostej czy okręgu należącym do zbioru $|𝒵.$ Wtedy $|𝒳n+1 = 𝒳n ∪ {P}.$ Rozważmy zbiór $𝒳,$ będący sumą wszystkich zbiorów $|𝒳n.$ Zauważmy, że zbiór $𝒳$ zawiera nieskończenie wiele elementów. Ponadto żadne trzy punkty należące do tego zbioru nie są współliniowe, a żadne cztery nie leżą na jednym okręgu. Zatem zbiór $|𝒳$ jest szukanym przez nas zbiorem.

Jak, mając taki zbiór, możemy pokolorować płaszczyznę tak, by każda prosta była co najwyżej trzykolorowa, a każdy okrąg co najwyżej czterokolorowy? Pokolorujmy całą płaszczyznę jednym kolorem. Następnie weźmy taki zbiór punktów $|𝒳$ o nieskończonej liczbie elementów, że żadne trzy punkty, które do niego należą, nie są współliniowe, żadne cztery nie leżą na jednym okręgu. Każdy punkt należący do zbioru $𝒳$ pokolorujmy innym kolorem. Wtedy każda prosta będzie co najwyżej trzykolorowa, a każdy okrąg co najwyżej czterokolorowy. Rozwinięte zadanie z Olimpiady Matematycznej Juniorów okazało się bardzo ciekawym problemem. Obecnie pracuję nad jego uogólnieniem w trzecim wymiarze.

Kończąc, chciałabym bardzo podziękować opiekunowi mojej pracy, Panu Wojciechowi Guzickiemu za zaproponowanie mi tego tematu oraz pomoc przy tworzeniu pracy.