Przeskocz do treści

Delta mi!

Loading

Kolorowanie wielomianów

Tomasz Idziaszek

o artykule ...

  • Publikacja w Delcie: październik 2008
  • Publikacja elektroniczna: 04-06-2013
  • Wersja do druku [application/pdf]: (121 KB)

Za pomocą kolorowania wielomianów można udowodnić Zasadnicze twierdzenie algebry w zaskakująco elementarny sposób...

obrazek

Rys. 1 Striangulowany wielokąt; kolorem wyróżniono trójkąty i odcinki odgrywające rolę w lemacie Spernera.

Rys. 1 Striangulowany wielokąt; kolorem wyróżniono trójkąty i odcinki odgrywające rolę w lemacie Spernera.

Lemat Spernera

Narysujmy na płaszczyźnie wielokąt i dokonajmy jego triangulacji, czyli podziału na trójkąty, które mogą stykać się z innymi trójkątami wspólną krawędzią lub wspólnym wierzchołkiem (jak na rysunku 1). Wierzchołki tych trójkątów „pokolorujemy”, tzn. każdemu z nich przypiszemy jego „kolor” – liczbę ze zbioru math

Wyróżnijmy trójkąty, które mają wierzchołki wszystkich trzech kolorów. Jeśli poruszając się po obwodzie trójkąta przeciwnie do ruchu wskazówek zegara widzimy liczby w kolejności 0, 1, 2, to mamy do czynienia z trójkątem „dodatnio zorientowanym”. Oznaczmy liczbę takich trójkątów przez math natomiast liczbę trójkątów „ujemnie zorientowanych” przez math

Interesować nas też będą krawędzie na brzegu wielokąta. Jeżeli wierzchołki takiej krawędzi mają kolory math i  math (przy czym kolor math ma wierzchołek, który napotykamy najpierw, gdy poruszamy się po obwodzie wielokąta przeciwnie do ruchu wskazówek zegara), to taką krawędź nazwiemy math Wyróżnimy krawędzie, które mają kolory 0 i 1. Krawędzie 01 nazwiemy „dodatnio zorientowanymi”, natomiast krawędzie 10 będą „ujemnie zorientowane”. Ich liczbę oznaczymy, odpowiednio, przez math  i  math

obrazek

Rys. 2 Ilustracja dowodu lematu Spernera.

Rys. 2 Ilustracja dowodu lematu Spernera.

Ciekawy lemat (znany jako skierowana wersja lematu Spernera) podaje zależność między tym, co musi się dziać wewnątrz takiego striangulowanego wielokąta, a tym, co się dzieje na jego brzegu – mianowicie

display-math(*)

Dowód. Dowód lematu jest bardzo prosty. Przetnijmy każdą z krawędzi 01 i 10 prostopadłym wektorem (w kierunku takim, jak na rysunku 2) i utwórzmy z tych wektorów graf. Graf ten składa się ze skierowanych ścieżek. Każda ścieżka zaczyna się w ujemnie zorientowanym trójkącie lub na dodatnio zorientowanym odcinku, natomiast kończy się w dodatnio zorientowanym trójkącie lub na ujemnie zorientowanym odcinku. Liczba początków math  musi być równa liczbie końców ścieżek math , co dowodzi równości math



Liczby zespolone

O liczbach zespolonych (ich zbiór będziemy oznaczać przez math) możemy myśleć jak o wektorach (postaci math) na płaszczyźnie. Na liczbach tych możemy wykonywać działania. Dodawanie wykonuje się dokładnie tak samo jak dodawanie wektorów. Aby zdefiniować mnożenie, potrzebne są nam dwa pojęcia. Argumentem liczby zespolonej math nazywamy kąt, który tworzy ona z wektorem math i oznaczamy go przez math (Argument jest dany z dokładnością do math tzn. jeżeli math jest argumentem math to math też. W dalszym ciągu ta niejednoznaczność nie będzie nam przeszkadzała. Przyjmujemy także, że math) Modułem liczby zespolonej math nazywamy długość wektora reprezentującego math i oznaczamy go przez math Łatwo zauważyć, że math i  math jednoznacznie wyznaczają liczbę math

Wynikiem mnożenia dwóch liczb math i math jest liczba zespolona math o argumencie math i module math

Teraz, gdy umiemy już dodawać i mnożyć, możemy zdefiniować wielomian zmiennej zespolonej (analogicznie jak wielomian zmiennej rzeczywistej): wielomianem stopnia math zmiennej zespolonej math będziemy nazywać funkcję math  daną wzorem

display-math

gdzie math są liczbami zespolonymi oraz math

Zasadnicze twierdzenie algebry głosi, że każdy wielomian dodatniego stopnia zmiennej zespolonej ma co najmniej jeden pierwiastek. Jest wiele dowodów tego ważnego twierdzenia, ale lemat Spernera pomoże nam je udowodnić w zaskakująco elementarny sposób.

Kolorowanie

Ustalmy wielomian math  Przez kolorowanie wielomianu nazwiemy kolorowanie płaszczyzny zespolonej math trzema kolorami 0, 1, 2 w zależności od argumentu liczby zespolonej math  Kolor math -ty otrzymają liczby ze zbioru

display-math

Tak pokolorowaną płaszczyznę (Rys. 3) oznaczmy przez math

Popatrzmy na kilka przykładów. Jeśli wielomian math  będzie stopnia 0, to cała płaszczyzna będzie jednokolorowa. Jeśli wielomian będzie postaci math to płaszczyzna będzie podzielona na trzy przystające kąty o wspólnym wierzchołku w punkcie math Będzie to wyglądało tak samo jak na rysunku 3, tylko punkt zbiegu kolorów będzie leżał gdzie indziej.

Aby pokolorować wielomian math  sięgniemy do definicji mnożenia liczb zespolonych. Mamy math zatem jeśli punkt math dostał kolor 0, to math lub math Analogiczne rozumowanie w przypadku kolorów 1 i 2 prowadzi nas do wniosku, że math jest podzielona na sześć przystających kątów o wierzchołkach w punkcie math (patrz rysunek 4).

Nietrudno się przekonać o tym, że kolorując math  będziemy musieli namalować math przystających kątów. Będą one miały kolejno kolory 0, 1, 2, 0, 1, 2 itd.

Do tej pory szło nam łatwo, ale już w przypadku wielomianu math napotykamy kłopoty. Z pomocą komputera możemy wygenerować kolorowanie tego i innych wielomianów (rysunki 5 i 6, a także okładka). Obserwując obrazki, możemy dojść do dwóch wniosków:

  • Łatwo na rysunku znaleźć zera wielomianu. Są to dokładnie te punkty, w których zbiegają się wszystkie trzy kolory.
  • Niech math  będzie wielomianem stopnia math  Im dalej od punktu math tym bardziej kolorowanie math przypomina kolorowanie math

Pierwszy z wniosków wynika z ciągłości math  Dla dowodu drugiego zauważmy, że przy math  mamy math zatem poza dostatecznie dużym kołem math o środku w punkcie math będzie wyglądało prawie jak math

obrazek

Rys. 7 Ilustracja dowodu zasadniczego twierdzenia algebry. Kolorowanie wielomianu math Poza wielokątem math  wielomian wygląda jak math

Rys. 7 Ilustracja dowodu zasadniczego twierdzenia algebry. Kolorowanie wielomianu math Poza wielokątem math  wielomian wygląda jak math

Wiemy zatem, co się dzieje poza dużym kołem math tym bardziej wiemy też, co się dzieje poza dowolnym wielokątem wypukłym math  zawierającym to koło. Nie wiemy jednak, co się dzieje w jego wnętrzu, ale spróbujemy to odgadnąć, badając jego brzeg. Do tego przyda nam się lemat Spernera. Dokonajmy triangulacji wielokąta math  i pokolorujmy jego wierzchołki. Kolorowanie będzie wyznaczone przez math (patrz rysunek 7). Jeśli trójkąty są dostatecznie małe, to na brzegu pojawią się tylko krawędzie math i  math Krawędzi math jest dokładnie math (znowu przy założeniu dostatecznie drobnej triangulacji), zatem math

Analogicznie, brak krawędzi math powoduje, że math  i prawa strona równania math jest równa math Wynika z tego, że math zatem w wielokącie math  istnieje trójkąt trójkolorowy.

Zdefiniujmy teraz taki ciąg triangulacji math że średnica największego trójkąta w  math dąży do 0 przy math W triangulacji math znajdziemy trójkolorowy trójkąt o wierzchołkach math i  math (punkt math ma kolor math). Ponieważ ciąg punktów math jest ograniczony przez wielokąt math  więc na podstawie twierdzenia Bolzano-Weierstrassa można z niego wybrać podciąg zbieżny math Z tego, co powiedzieliśmy o średnicach, wynika, że podciągi math i  math również są zbieżne do tej samej granicy math

Widać zatem, że w punkcie math  zbiegają się wszystkie trzy kolory, zatem math  co kończy dowód zasadniczego twierdzenia algebry.

Notice: Undefined index: story_alias_uuid in /home/misc/deltami/public_html/ui/inc/site_php_include/index.inc on line 23 Notice: Undefined index: story_alias_uri in /home/misc/deltami/public_html/ui/inc/site_php_include/index.inc on line 24