LIV OM - III - Zadanie 6

Zawody matematyczne:

LIV OM, 2002-2003

Etap:

III

Niech n będzie dodatnią liczbą całkowitą parzystą. Udowodnić, że istnieje permutacja $(x_1,x_2, \ldots ,x_n)$ zbioru $\{1,2,\ldots,n\}$ , spełniająca dla każdego $i \in \{1,2,\ldots ,n\}$ warunek:

$x_{i+1}$ jest jedną z liczb $2x_i$ , $2x_i-1$ , $2x_i-n$ , $2x_i-n-1$ ,

przy czym $x_{n+1} = x_1$ .

Rozwiązanie

Przyjmijmy oznaczenia:

$f(x)= \left\{\begin{array}{ll} 2x&\textrm{gdy}\ x \leq n/2,\\ 2x-n&\textrm{gdy}\ x>n/2,\\ \end{array}\right. $

$ g(x)=f(x)-1. $

Rozważamy graf skierowany o $n$ wierzchołkach ponumerowanych $1,2,\ldots,n$ , w którym z punktu (wierzchołka) $x$ wychodzą dwie zorientowane krawędzie: do punktu $f(x)$ i do $g(x)$ . Teza sprowadza się do istnienia zamkniętej ścieżki, przechodzącej przez każdy wierzchołek dokładnie jeden raz (cyklu Hamiltona).

Startując od wierzchołka o numerze $1$ i działając funkcjami $f$ , $g$ , możemy uzyskać: w jednym kroku - punkty $1$ i $2$ ; w dwóch krokach - punkty $1$ , $2$ , $3$ , $4$ ; w trzech krokach - punkty od $1$ do $8$ ; itd. Widać, że każdy punkt jest osiągalny z wierzchołka $1$ .

Niech $S: x_1 \to x_2 \to \ldots \to x_m$ będzie najdłuższą ścieżką, przechodzącą przez różne wierzchołki, wśród których jest wierzchołek o numerze $1$ . Obie wychodzące z punktu $x_m$ krawędzie trafiają w pewne punkty ścieżki $S$ (w przeciwnym razie ścieżkę dałoby się przedłużyć). Mamy więc krawędzie $x_m \to x_k$ , $x_m \to x_\ell$ ( $k,\ell \leq m$ , $k \neq \ell$ ); niech np. $f (x_m) = x_k$ , $g(x_m) = x_\ell$ .

Przypuśćmy, że $k,\ell> 1$ . Wówczas

$ x_k \in \{f (x_{k-1}),g(x_{k-1})\},\ x_\ell \in \{f (x_{\ell-1}),g(x_{\ell-1})\}. $

Funkcja $f$ przyjmuje tylko wartości parzyste, a $g$ wartości nieparzyste. Ponadto każda z równości $f (x) = f (y)$ i $g(x) = g(y)$ implikuje $x \equiv y (\mathrm{mod}\ n/2)$ . Zatem

$ x_k=f(x_{k-1})=f(x_m),\ x_\ell=g(x_{\ell-1})=g(x_m), $

skąd $x_m \equiv x_{k-1} \equiv x_{\ell-1} (\mathrm{mod}\ n/2)$ - sprzeczność, bo $x_m, x_{k-1}, x_{\ell- 1}$ są trzema różnymi liczbami ze zbioru $\{1, 2, \ldots , n\}$ .

Zatem $k = 1$ lub $\ell =1$ , co oznacza, że $x_m \to x_1$ jest krawędzią grafu. Uzupełnia ona ścieżkę $S$ do zamkniętego cyklu. Załóżmy, że poza nią pozostały jakieś wierzchołki grafu. Są one osiągalne z wierzchołka o numerze $1$ (leżącego na ścieżce $S$ ). Zatem z pewnego punktu tej ścieżki, $x_p$ , musi wychodzić krawędź do punktu $y$ leżącego poza nią. Wtedy $x_{p+1} \to \ldots \to x_m \to x_1 \to \ldots \to x_p \to y$ jest ścieżką przechodzącą przez $m+1$ różnych wierzchołków (wśród których jest punkt $1$ ), wbrew maksymalności $m$ .

Wniosek: ścieżka $S$ , uzupełniona krawędzią $x_m \to x_1$ , jest cyklem przechodzącym przez wszystkie wierzchołki grafu.