Delta
  Wiw.pl   Na bieżąco:  Informacje   Co nowego   Matematyka i przyroda:  Astronomia   Biologia   Fizyka   Matematyka   Modelowanie rzeczywistości   Humanistyka:  Filozofia   Historia   Kultura antyczna   Literatura   Sztuka   Czytaj:  Biblioteka   Delta   Wielcy i więksi   Przydatne:  Słowniki   Co i gdzie studiować   Wszechświat w obrazkach    
  Jesteś tutaj:  Wirtualny Wszechświat > Delta > Matematyka - spis artykułów >  STRAŻNICY W MUZEUM  
  Jesteś tutaj
Wybór artykułów z miesięcznika "Delta"
"Delta" to miesięcznik popularyzujący matematykę, fizykę i astronomię na bardzo wysokim poziomie, wydawany od 1974 roku.
Wirtualny Wszechświat prezentuje wybór tekstów publikowanych w "Delcie" od pierwszego numeru po początek XXI wieku.
  Szukacz
Delta 11/1999
Marek KORDOS, Paweł STRZELECKI
STRAŻNICY W MUZEUM

Przypuśćmy, że muzeum ma kształt wielokąta o m bokach (niekoniecznie wypukłego), a jego dyrektor chciałby mieć pewność, że wszystkie punkty muzeum znajdują się stale pod obserwacją strażników, którzy stoją w miejscu, ale mogą się obracać. Ilu strażników powinien zatrudnić? Zakładamy, że muzeum nie ma dziur wewnątrz, tzn. jego brzeg tworzy jedna łamana zamknięta, która nie ma samoprzecięć.

Oczywiście, gdy wielokąt tworzący muzeum jest wypukły, wystarczy jeden strażnik, postawiony w dowolnym punkcie. Czytelnik bez trudu wskaże przykłady muzeów, które wypukłe nie są, lecz mimo to do ich upilnowania wystarcza jeden strażnik. Takie wielokąty nazywamy gwiaździstymi.

Czasem potrzeba więcej strażników. Rozpatrzmy muzeum w kształcie grzebienia, które ma m = 3k ścian (rysunek 1). Każde z ostrzy zębów grzebienia - na rysunku zaznaczonych kolorowymi kropkami - można obserwować tylko z punktów zacieniowanego trójkąta, który dane ostrze zawiera. Tego muzeum musi więc pilnować przynajmniej k strażników i oczywiście tylu wystarczy: trzeba ich ustawić np. na odcinkach oznaczonych kolorowymi kreskami.

Rys. 1.

Odcinając z muzeum w kształcie grzebienia jeden lub dwa narożniki, przekonamy się, że dla każdej liczby m (nie tylko dla rozpatrzonych przed chwilą m podzielnych przez 3) istnieje muzeum o m bokach, którego musi pilnować przynajmniej [m/3] strażników.

Okazuje się, że gorszego przypadku wymyślić nie sposób, zachodzi bowiem następujące twierdzenie, które udowodnił ćwierć wieku temu Vaclav Chvátal:

Twierdzenie: Do pilnowania dowolnego wielokąta muzeum o m ścianach wystarczy [m/3] strażników.

Dla dowodu narysujmy m - 3 przekątnych muzeum, dobranych tak, by podzielić muzeum na m - 2 trójkąty (rysunek 2). Zawsze można to zrobić, na ogół na wiele sposobów; nie jest ważne, który z nich wybierzemy. Gdy wierzchołki muzeum oznaczymy kropkami, powstanie graf. Okazuje się, że jest to zawsze graf trójkolorowalny: jego wierzchołki można pomalować trzema kolorami w taki sposób, żeby każde dwa wierzchołki, które są połączone odcinkiem, miały różne kolory. Udowodnimy to przez indukcję względem m.

Rys. 2.

Gdy m = 3, nie ma czego dowodzić: każdy z wierzchołków malujemy innym kolorem. Przypuśćmy teraz, że m > 3 i załóżmy, że dla wszystkich liczb m', mniejszych od m, otrzymany graf jest trójkolorowalny. Weźmy którekolwiek dwa wierzchołki połączone przekątną; dzieli ona cały graf na dwa mniejsze grafy tego samego typu. Korzystając z założenia indukcyjnego, kolorujemy najpierw jeden z nich, a potem drugi, w razie potrzeby dokonując przy drugim malowaniu permutacji kolorów, tak aby uzgodnić kolory obu końców wybranej przekątnej. To kończy dowód postawionej hipotezy.

Teraz wszystko jest już niemal oczywiste: ponieważ mamy m wierzchołków pomalowanych trzema kolorami, więc istnieje kolor - powiedzmy kolor czerwony - którym pomalowano nie więcej niż [m/3] wierzchołków. Strażników należy ustawić właśnie w tych wierzchołkach; każdy z trójkątów, na które przekątne dzielą muzeum, ma wierzchołek czerwony, a zatem każdego trójkąta z pewnością pilnuje przynajmniej jeden strażnik. Skoro tak, to i całe muzeum znajduje się pod obserwacją.

Istnieją różne wersje i odmiany zadania o strażnikach w muzeum. Wspomnijmy o jednej z nich, która do dziś czeka na to, aż jakiś wystarczająco zdolny i zapalony człowiek ją rozwiąże. Nadal rozpatrujemy muzeum o m ścianach, takie, jak poprzednio, jednak tym razem zakładamy, że każdy ze strażników może spacerować wzdłuż jednej ze ścian i widzi wszystko, co można zobaczyć z dowolnego punktu leżącego gdziekolwiek na tej ścianie. Ilu spacerujących strażników musi pilnować muzeum?

Rys. 3.

Łatwo podać, w ślad za Gottfriedem Toussaintem, przykład muzeum o m = 4s ścianach, do którego upilnowania potrzeba przynajmniej s spacerujących strażników. Rysunek 3 przedstawia ten przykład dla s = 3; Czytelnik bez trudu wskaże, wzdłuż których ścian powinni spacerować strażnicy. Nie wiadomo natomiast, czy w muzeum o m ścianach [m/4] spacerujących strażników zawsze wystarczy; istnieje hipoteza, która głosi, że tak, być może z wyjątkiem pewnych niezbyt dużych wartości m. Może więc ci z Czytelników, którym marzą się matematyczne ostrogi, spróbują swych sił?




[góra strony]
Wiw.pl  |  Na bieżąco  |  Informacje  |  Co nowego  |  Matematyka i przyroda  |  Astronomia  |  Biologia  |  Fizyka  |  Matematyka  |  Modelowanie rzeczywistości  |  Humanistyka  |  Filozofia  |  Historia  |  Kultura antyczna  |  Literatura  |  Sztuka  |  Czytaj  |  Biblioteka  |  Delta  |  Wielcy i więksi  |  Przydatne  |  Słowniki  |  Co i gdzie studiować  |  Wszechświat w obrazkach