XXXIV OM - I - Zadanie 7

Niech $ S_n $ będzie zbiorem ciągów długości $ n $ o wyrazach $ -1 $, $ +1 $. Określamy funkcję $ f: S_n - \{(-1, 1, 1,\ldots, 1)} \to S_n $ jak następuje: jeśli $ (a_1, \ldots, a_n) \in S_n - \{(-1, 1, 1,\ldots, 1)\} $ i $ k = \max_{1\leq j \leq n} \{j \;:\; a_1\cdot a_2\cdot \ldots \cdot a_j = 1\} $, to $ f(a_1,\ldots, a_n) = (a_1, \ldots, a_{k-1}, -a_k, a_{k+1}, \ldots, a_n) $. Udowodnić, że

\[<br />
\underbrace{f\circ f\circ \ldots \circ f}_{2^n-1}(1, 1, \ldots, 1)= (-1,1,1, \ldots, 1).<br />
\]

Rozwiązanie

Dla uproszczenia zapisu wprowadzimy symbol $ f^{(k)} $ na oznaczenie $ k $-krotnej iteracji funkcji $ f $:

\[<br />
f^{(k)} = \underbrace{f \circ f \circ \ldots \circ f}_k<br />
\]

Tezę zadania udowodnimy indukcyjnie. Określenie funkcji $ f $ zależy oczywiście od liczby naturalnej $ n $. Tam, gdzie pomoże to uniknąć nieporozumień będziemy pisali $ f_n $ zamiast $ f $ aby wyeksponować wartość liczby naturalnej $ n $.

Udowodnimy najpierw dwa lematy.

Lemat 1. Jeśli $ m $, $ n $ są liczbami naturalnymi i $ f_n^{(2m)}(1, 1, \ldots, 1)= (a_1, a_2, \ldots, a_n) $, to $ a_1a_2 \ldots a_n=1 $.

Dowód. Z określenia funkcji $ f $ wynika, że jeśli $ f(b_1, b_2, \ldots, b_n)= (c_1, c_2, \ldots, c_n) $, to $ c_1c_2\ldots c_n = -b_1 b_2 \ldots b_n $. Zatem parzystokrotne złożenie funkcji $ f $ przyporządkowuje ciągowi $ (1, 1,\ldots, 1) $ ciąg, którego wyrazy dają w iloczynie $ 1 $.

Lemat 2. Jeżeli $ f_n^{(m)} (1,1,\ldots,1) = (a_1, a_2, \ldots, a_n) $, to $ f_{n+1}^{(2m)}(1, 1, \ldots,1)= (a_1, a_2, \ldots, a_n, a) $, gdzie $ a = 1 $ lub $ a = - 1 $.

Dowód. Zastosujemy indukcję względem $ m $.

Jeśli $ m= 1 $, to $ f_n(1, 1,\ldots, 1)= (1, 1,\ldots, 1, - 1) $, natomiast $ f_{n+1}^{(2)} (1,1,\ldots,1) = f_{n+1}(1,1,\ldots, 1,-1)= (1,1,\ldots,-1,-1) $.

Załóżmy, że dla pewnego $ m $ jeśli $ f_n^{(m)}(1,1,\ldots, 1) =(a_1,a_2,\ldots,a_n) $, to $ f_{n+1}^{(2m)}(1,1,\ldots, 1) =(a_1, a_2,\ldots,a_n, a) $. Z określenia funkcji $ f $ wynika, że $ f_n^{(m+1)}(1,1,\ldots, 1 =f_n(a_1, a_2, \ldots, a_n)= (a_1, a_2, \ldots, -a_k, \ldots, a_n) $. Na podstawie lematu 1 $ a_1a_2\ldots a_na= 1 $, zatem $ f_{n+1}(a_1, a_2, \ldots, a_n, a)= (a_1, a_2, \ldots, a_n, -a) $, więc przyjmując $ a_{n + 1} = -a $ mamy $ f_{n+1}(a_1,a_2,\ldots, a_n,a)= (a_1, a_2, \ldots, a_n, a_{n+1}) $. Ponieważ $ a_1a_2\ldots a_{n + 1} = - 1 $, więc

\[<br />
\max_{1 \leq j \leq n+1} \{j \colon a_1a_2\ldots a_j = 1\}= \max_{1 \leq j \leq n} \{ j \colon a_1a_2\ldots a_j=1 \},<br />
\]

a stąd wynika, że $ f_{n+1}(a_1, a_2, \ldots, a_{n+1})= (a_1,a_2,\ldots,-a_k, \ldots, a_{n+1}) $. Wobec tego $ f_{n+1}^{(2(k+1))}(1, 1, \ldots, 1)= f_{n+1}^{(2)} (a_1, a_2, \ldots, a_n, -a_{n+1}) = (a_1, a_2, \ldots, -a_k, \ldots, a_n, a_{n+1}) $. Kończy to dowód kroku indukcyjnego. Na mocy zasady indukcji teza lematu jest spełniona dla każdego naturalnego $ k $.

Przystąpimy obecnie do dowodu twierdzenia sformułowanego w treści zadania.

Dla $ n =2 $ twierdzenie jest oczywiście spełnione.

Załóżmy dla pewnego $ n $, że

\[<br />
f_{n}^{(2^n-1)} (1,1,\ldots,1)=(-1, 1,1,\ldots, 1)<br />
\]

Na podstawie lematu 2

\[<br />
f^{(2(2^n-1))}(1,1,\ldots,1) = (-1, 1, \ldots,1, a),<br />
\]

gdzie $ a = 1 $ lub $ a = -1 $.

Z lematu 1 wynika jednak, że $ -1 \cdot 1 \cdot \ldots \cdot 1 \cdot  a = 1 $, więc $ a = - 1 $. Wobec tego

\[<br />
f_{n+1}^{(2^{n+1}-1)}(1,1,\ldots,1) = f_{n+1} f_{n+1}^{(2(2^{n-1}))}(1, 1, \ldots,1) =<br />
\]
\[<br />
\quad = f_{n+1}(-1, 1, \ldots,1, -1) = (-1, 1, \ldots, 1).<br />
\]

Na mocy zasady indukcji dla każdego $ n $ jest $ f^{2^{n-1}} (1,1,\ldots, 1)= (-1,1,\ldots, 1) $.

Komentarze

Dodaj nową odpowiedź