III MEMO - Zadanie 2

Dane jest $n\geq3$ różnych kolorów. Niech $f(n)$ będzie największą liczbą całkowitą o następującej własności: Możliwe jest takie pokolorowanie wszystkich boków i przekątnych wielokąta wypukłego o $f(n)$ wierzchołkach, że

wykorzystane są co najmniej dwa różne kolory,
każde trzy wierzchołki wielokąta wyznaczają trójkąt o wszystkich bokach jednakowego koloru lub o wszystkich bokach różnego koloru.

Dowieść, że $f(n)\leq(n-1)^2$ oraz że równość zachodzi dla nieskończenie wielu wartości $n$ .

Rozwiązanie

Dla $n\geq 3$ rozważmy wielokąt wypukły o $f(n)$ wierzchołkach. Krawędzią będziemy nazywać dowolny bok lub przekątną wielokąta. Załóżmy, że pomalowaliśmy krawędzie wielokąta zgodnie z regułami zadania, mając do dyspozycji kolory $1,2,\dots,n$ .

Niech $k_i(w)$ oznacza liczbę krawędzi o jednym końcu w wierzchołku $w$ , pomalowanych $i$ -tym kolorem, dla $i=1,2,\dots,n$ . Wtedy dla dowolnego wierzchołka $w$ zachodzi

$ (1) \qquad k_1(w)+k_2(w)+\dots+k_n(w)=f(n)-1. $

Przypuśćmy, że dla pewnego wierzchołka $w_0$ i $j$ -tego koloru (możemy przyjąć, że jest to kolor niebieski) zachodzi $k_j(w_0)\geq n-1$ . To oznacza, że istnieje $n-1$ niebieskich krawędzi, których końcem jest $w_0$ . Oznaczmy przez $w_1,w_2,\dots,w_{n-1}$ pozostałe końce tych krawędzi. Ze względu na (ii) wszystkie krawędzie o obu końcach w zbiorze $\{w_1,w_2,\dots,w_{n-1}\}$ muszą być niebieskie.

Wiadomo, że nie wszystkie krawędzie są niebieskie, istnieje zatem wierzchołek $v$ i krawędź łącząca go z jakimś wierzchołkiem ze zbioru $\{w_0,w_1,\dots,w_{n-1}\}$ , która nie jest niebieska. Bez starty ogólności możemy założyć, że krawędź o końcach $v,w_0$ jest czerwona. Wtedy każda krawędź o końcach $v,w_j$ , dla $j=1,2,\dots,n-1$ , nie może być ani czerwona, ani niebieska, ze względu na (ii). Rozważanych krawędzi jest $n-1$ , a kolorów, którymi zostały pomalowane, jest nie więcej niż $n-2$ , zatem istnieją dwie krawędzie, np. $vw_i$ i $vw_j$ , pomalowane tym samym kolorem (i nie jest to ani czerwony, ani niebieski). Zauważmy jednak, że wtedy trójkąt o wierzchołkach $v$ , $w_i$ , $w_j$ jest pomalowany dokładnie dwoma kolorami, co w świetle (ii) jest niemożliwe. Otrzymana sprzeczność dowodzi, że $k_j(w)<n-1$ dla każdego wierzchołka $w$ i kolorów $j=1,2,\dots,n$ .

Zatem, wracając do (1),

$ f(n)=1+k_1(w)+k_2(w)+\dots+k_n(w)\leq1+n(n-2)=(n-1)^2, $

co kończy rozwiązanie pierwszej części zadania.

Pozostaje uzasadnić, że równość zachodzi dla nieskończenie wielu wartości $n$ . Załóżmy, że $n-1=p$ i $p$ jest liczbą pierwszą. Przypiszmy każdemu wierzchołkowi $p^2$ -kąta wypukłego inną parę $(a,b)$ , dla $a,b\in\{1,2,\dots,p\}$ . Malujemy kolorem $p+1$ każdą krawędź łączącą wierzchołek $(a,b)$ i $(a',b)$ dla $a,b,b'\in\{1,2,\dots,p\}$ . Następnie dla $k=1,2,\dots,p$ , kolorem $k$ malujemy każdą krawędź łączącą wierzchołek $(a,b)$ i $(a',b')$ , która spełnia warunek: $b\neq b'$ oraz

$ (2) \qquad k(b-b')\equiv a-a'\pmod p. $

Wiadomo, że dla dowolnej niezerowej liczby całkowitej $x$ i całkowitej liczby $y$ istnieje dokładnie jedno takie $k\in\{1,2,\dots,p\}$ , że $kx\equiv y\pmod p$ , więc za pomocą (2) przypisaliśmy każdej krawędzi jeden kolor. Ponadto nietrudno sprawdzić, że nie wszystkie krawędzie wielokąta są pomalowane tym samym kolorem.

Sprawdźmy, że spełniony jest również warunek (ii). Rozważmy trzy różne wierzchołki $(a,b)$ , $(a',b')$ , $(a'',b'')$ oraz przypuśćmy, że krawędź łącząca $(a,b)$ i $(a',b')$ jest tego samego koloru $k$ co krawędź łącząca $(a,b)$ i $(a'',b'')$ .

Jeżeli $k=p+1$ , to $b=b'$ i $b=b''$ , a stąd $b'=b''$ i z definicji naszego kolorowania wynika, że krawędź łącząca $(a',b')$ i $(a'',b'')$ jest pomalowana kolorem $p+1$ .

Jeżeli zaś $k\neq p+1$ , to $b\neq b'$ , $b\neq b''$ oraz

$ k(b-b')\equiv a-a'\pmod p\quad\text{i}\quad k(b-b'')\equiv a-a''\pmod p. $

Wtedy $kb'-a'\equiv kb-a\equiv kb''-a''\pmod p$ , zatem

$ k(b'-b'')\equiv a'-a''\pmod p. $

To oznacza, że $b'\neq b''$ i krawędź łącząca $(a',b')$ z $(a'',b'')$ jest koloru $k$ .

Pokazaliśmy, że nie istnieje trójkąt, którego boki byłyby pomalowane dokładnie dwoma kolorami, a tym samym sprawdziliśmy (ii). Powyższe kolorowanie krawędzi $p^2$ -kąta $p+1$ kolorami spełnia warunki zadania, czyli $f(p+1)\geq p^2$ . Wobec wcześniejszych rozważań zachodzi $f(p+1)=p^2$ , a ponieważ liczbę pierwszą $p$ możemy wybrać na nieskończenie wiele sposobów, wskazaliśmy nieskończenie wiele przypadków, w których $f(n)=(n-1)^2$ .