XLVIII OM - II - Zadanie 3

Zawody matematyczne:

XLVIII OM, 1996-1997

Etap:

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ż

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

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.