XLVIII OM - II - Zadanie 3

Dany jest zbiór $ n $ punktów ($ n \geq 2 $), z których żadne trzy nie leżą na jednej prostej. Kolorujemy wszystkie odcinki o końcach w tym zbiorze tak, by każde dwa odcinki o wspólnym końcu miały różne kolory. Wyznaczyć najmniejszą liczbę kolorów, dla której istnieje takie pokolorowanie.

Rozwiązanie

Przyjmijmy, że dane punkty są wierzchołkami pewnego $ n $-kąta (jeśli $ n = 2 $, wystarczy oczywiście jeden kolor). Wszystkie odcinki o jednakowym kolorze wyznaczają rozłączne pary wierzchołków wielokąta. Maksymalna liczba rozłącznych podzbiorów dwuelementowych zbioru $ n $-elementowego wynosi $ [n/2] $. Zatem liczba kolorów jest nie mniejsza niż

\[<br /> {n \choose 2}\left[\frac{n}{2}\right]^{-1}=\left\{<br /> \begin{array}{cl}<br /> n & \textrm{dla $n$ nieparzystych},\\<br /> n-1 & \textrm{dla $n$ parzystych}.<br /> \end{array}\right.<br /> \]

Wykażemy, że ta liczba kolorów wystarcza do spełnienia żądanego warunku.

Gdy $ n $ jest liczbą nieparzystą, bierzemy zbiór wierzchołków $ n $-kąta foremnego i malujemy jednakowym kolorem bok i wszystkie równoległe do niego przekątne; odcinki nierównoległe malujemy różnymi kolorami. Użyliśmy $ n $ kolorów.

Gdy $ n $ jest liczbą parzystą, bierzemy zbiór wierzchołków $ (n-1) $-kąta foremnego $ V $ oraz jeszcze jeden punkt $ P_0 $. Kolorujemy boki i przekątne wielokąta $ V $ w sposób opisany powyżej, używając $ n - 1 $ kolorów. Dla każdej rodziny równoległych odcinków jednakowego koloru $ k_i $, pozostaje jeden wierzchołek $ P_i $ wielokąta $ V $ nie będący końcem żadnego z tych odcinków. Malujemy odcinek $ P_0P_i $, kolorem $ k_i $. Użyliśmy $ n - 1 $ kolorów, spełniając wymagany warunek.

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

Komentarze

Dodaj nową odpowiedź