Question

sejam {1,2,3,4,5} e f uma função definida por: f(1)=4,f(2)=1,f(3)=3,f(4)=5, e f(5)=2 se para n>1, f**n(x)=f(f**n-1(X)) determine o valor de f**2021(X)

Answer 1

Dada a função definida $f: \{1,2,3,4,5\}\rightarrow \{1,2,3,4,5\}$

$f(1) = 4\\f(2) = 1\\f(3) = 3\\f(4)=5\\f(5)=2$

Definimos a composta de si mesma pela recursão

$f^n(x) = f(f^{n-1}(x))$

Ou seja, a cada relação, a função se auto alimenta. Como f é bijetora e seu domínio tem um número finito de elementos, haverá alguma hora, necessariamente que

$f^k(x) = x$

Para valores específicos de k.

Prova: Como f é bijetora e o domínio é finito e é igual ao contradomínio, sempre haverá uma cadeia que liga um elemento ao outro por f. Para 1 elemento isto é trivial, já que a função leva um número a ele mesmo, agora suponha que para um conjunto de n elementos sempre haverá

$f: \{x_1, \dots, x_n\}\rightarrow \{x_1, \dots, x_n\}$

f é bijetora, ou seja, cada valor do domínio leva à um único valor no contradomínio, e mais, todo valor do contradomínio leva à um único valor no domínio pela inversa de f, suponha que começamos com um valor do domínio y₁, nossa função nos leva até outro valor que pode ser ele mesmo, ou outro valor, y₂. Se f(y₁) = y₁, então criamos um ciclo como no caso de 1 elemento e partimos para o próximo elemento, se f(y₁) = y₂ continuamos para ele. Em y₂, não podemos fazer o mesmo que fizemos antes, pois se f(y₂) = y₂, f não seria injetora, portanto podemos ter que f(y₂) = y₁, criando um loop de 2 elementos, seguindo para o próximo, ou f(y₂) = y₃, e continuamos nele.

Em geral fazemos o seguinte passo lógico

Para $1\leq k \leq n$, $f(y_k)$  pode assumir 2 valores possíveis,

$f(y_k)=y_1$

ou

$f(y_k) = f(y_{k+1})$

Caso feche o loop, na primeira opção, retiramos os elementos que se repetem do nosso conjunto e escolhemos um novo y₁ deste novo conjunto.

Quando chegamos ao último elemento ele só pode fechar o loop, pois não há qualquer outro elemento para continuar.

Portanto, existe uma partição do domínio de f de pelo menos 1 conjunto, em que os elementos se repetem, ou seja,

$\displaystyle y_1^{(1)} \xrightarrow{f} y_2^{(1)} \xrightarrow{f} \dots \xrightarrow{f} y_{n_1}^{(1)} \xrightarrow{f} y_1^{(1)}$

$.\hspace{2.4cm} \vdots$

$\displaystyle y_1^{(\ell)} \xrightarrow{f} y_2^{(\ell)} \xrightarrow{f} \dots \xrightarrow{f} y_{n_\ell}^{(\ell)} \xrightarrow{f} y_1^{(\ell)}$

Neste caso haveriam $\ell$ loops de $n_\ell$ elementos cada loop. Com isso, provamos que

$f^{n_j}(y_i^{(j)}) = y_i^{(j)}$

Ou, para k específicos e todo x no domínio,

$f^k(x) = x$

Q.E.D.    

Finalmente para o exercício, perceba que existe 2 loops, um com 4 elementos e outro com somente 1,

$1 \xrightarrow{f} 4 \xrightarrow{f} 5 \xrightarrow{f} 2 \xrightarrow{f} 1$

$3 \xrightarrow{f} 3$

Obtemos portanto, caso x pertença ao primeiro loop,

$f^{4k}(x) = x,\hspace{0.5cm} k\in\mathbb{N}$

Como 2021 = 4*505+1,

$f^{2021}(x) = f(f^{2020}(x)) = f(f^{4*505}(x)) = f(x)$

Já no segundo loop, como é de 1 elemento só é trivial que

$f^{2021}(3) = 3 = f(3)$

Portanto, para qualquer valor de x no domínio,

$f^{2021}(x) = f(x)$

$f^{2021}(1) = 4\\f^{2021}(2) = 1\\f^{2021}(3) = 3\\f^{2021}(4)=5\\f^{2021}(5)=2$