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

$ \underbrace{f\circ f\circ \ldots \circ f}_{2^n-1}(1, 1, \ldots, 1)= (-1,1,1, \ldots, 1). $

Rozwiązanie

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

$ f^{(k)} = \underbrace{f \circ f \circ \ldots \circ f}_k $

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

$ \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 \}, $

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$ .