Przeskocz do treści

Delta mi!

Loading

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

Jadwiga Czyżewska

o artykule ...

  • Publikacja w Delcie: maj 2017
  • Publikacja elektroniczna: 1 maja 2017
  • Autor: Jadwiga Czyżewska
    Afiliacja: Uczennica XIV LO im. Stanisława Staszica w Warszawie
  • Wersja do druku [application/pdf]: (755 KB)
  • Autorka jest laureatką XXXVII Konkursu Uczniowskich Prac z Matematyki w 2015 roku.

  • Artykuł jest skróconą wersją pracy nagrodzonej brązowym medalem w XXXVII Konkursie Uczniowskich Prac z Matematyki. Praca została następnie zakwalifikowana do europejskiego finału Konkursu Młodych Naukowców UE (EUCYS), której organizatorem w Polsce z ramienia Komisji Europejskiej jest Krajowy Fundusz na rzecz Dzieci.

O kolorowaniu płaszczyzny raz jeszcze...

obrazek

Rys. 1

Rys. 1

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.

obrazek

Rys. 2

Rys. 2

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.

obrazek

Rys. 3

Rys. 3

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

obrazek

Rys. 4

Rys. 4

obrazek

Rys. 5

Rys. 5

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.

obrazek

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.


Od Redakcji

Artykuł jest skróconą wersją pracy nagrodzonej brązowym medalem w XXXVII Konkursie Uczniowskich Prac z Matematyki. Praca została następnie zakwalifikowana do europejskiego finału Konkursu Młodych Naukowców UE (EUCYS), której organizatorem w Polsce z ramienia Komisji Europejskiej jest Krajowy Fundusz na rzecz Dzieci.