LIV OM - III - Zadanie 6

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)=<br />
\left\{\begin{array}{ll}<br />
2x&\textrm{gdy}\ x \leq n/2,\\<br />
2x-n&\textrm{gdy}\  x>n/2,\\<br />
\end{array}\right.<br />
\]
\[<br />
g(x)=f(x)-1.<br />
\]

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

\[<br />
x_k \in \{f (x_{k-1}),g(x_{k-1})\},\   x_\ell \in \{f (x_{\ell-1}),g(x_{\ell-1})\}.<br />
\]

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

\[<br />
x_k=f(x_{k-1})=f(x_m),\ x_\ell=g(x_{\ell-1})=g(x_m),<br />
\]

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.

Komentarze

Dodaj nową odpowiedź