Multime de functii cu ordinul 2008

[Filip Chindea]

Fie \( A \) multimea functiilor \( f : \mathbb{N} \rightarrow \mathbb{N} \) astfel încât pentru orice \( k \in \overline{1, 2007} \), \( f^{[k]} \neq \mathrm{Id}_{\mathbb{N}} \), iar \( f^{[2008]} \equiv \mathrm{Id}_{\mathbb{N}} \).
a) Sa se arate ca \( A \) este nevida.
b) Sa se determine daca \( A \) este infinita.
c) Demonstrati ca toate elementele lui \( A \) sunt functii bijective.
(Am notat cu \( \mathrm{Id} \) - functia identitate, iar prin \( f^{[k]} \) - compunerea lui \( f \) cu ea însasi de \( k \) ori).

[turcas]

Notam: x div 2008 = catul impartirii lui x la 2008 ;
x mod 2008 = restul impartirii lui x la 2008 ;

a) Gasim o functie care sa apartina lui \( A \).

\( f(x) = (x \text{ mod } 2008) + 1 + (x \text{ div } 2008) \cdot 2008 \) este o functie cu proprietatea ceruta, daca verificam \( f^{[2008]}(x) = x \). Deci \( A \) este nevida.

c) Avem proprietatea \( f \circ f \) - bijectiva, rezulta \( f \) - bijectiva. Cum \( f^{[2008]} \) - bijectiva \( \Rightarrow f \) este bijectiva.

[Filip Chindea]

Voi rezolva urmatoarea chestiune ceva mai generala:
Fie \( n \in \mathbb{N}^{\ast} \). Determinati \( A_n := \{f : \mathbb{N} \rightarrow \mathbb{N} \ : \ \forall k \in \overline{1, n - 1} \ , \ f^{[k]} \neq \mathrm{Id}_{\mathbb{N}} \ ; \ f^{[n]} \equiv \mathrm{Id}_{\mathbb{N}}\} \).
(Am notat cu \( \mathrm{Id} \) - functia identitate, iar prin \( f^{[k]} \) - compunerea lui \( f \) cu ea însasi de \( k \) ori)

Solutie. Fixam \( f \in A_n \). Pentru \( a \in \mathbb{N} \), sa notam \( <a> := \{ f^{[k]}(a) \ : \ k \in \mathbb{N}^{\ast} \} \). Cum \( f^{[n]}(a) = a \) rezulta ca \( <a> \) este finita, si notând \( \gamma(a) := | <a> | \) , se obtine \( \min \{k \in \mathbb{N}^{\ast} \ : \ f^{[k]}(a) = a \} = \gamma(a) \ | \ n \).
Sa presupunem ca pentru \( a, b \in \mathbb{N} \), exista \( x \in <a> \cap <b> \) si fie \( x = f^{[k]}(a) = f^{[l]}(b) \). Atunci \( f^{[k + t]}(a) = f^{[l + t]}(b) \in <b> \), oricare ar fi \( t \in \overline{1, \gamma(a)} \). Insa \( <a> = \{ f^{[k + t]}(a) \ : \ t \in \overline{1, \gamma(a)} \} \), deci \( <a> \subseteq <b> \). Din simetrie, si \( <b> \subseteq <a> \), deci \( <a> = <b> \).
Concluzionam ca exista \( M \subset \mathbb{N} \) astfel incat \( <a> \), cu \( a \in M \) determina o partitie a lui \( \mathbb{N} \). Cum \( f(<a>) = <a> \), avem \( \mathrm{Im} f = f(\mathbb{N}) = \bigcup_{a \in M} f(<a>) = \mathbb{N} \), si de aici punctul c).
Fie \( d \) cel mai mic multiplu comun al numerelor \( \gamma(a) \), \( a \in M \). Deci \( d | n \). Insa este clar ca \( f^{[d]} \equiv \mathrm{Id}_{\mathbb{N}} \), si astfel, conform definitiei multimii \( A_n \) avem \( d \ge n \). Deci \( d = n \).
Astfel, \( f \) este compunerea ciclurilor disjuncte
\( g_a(x) = \left\{ \begin{array}{ll} x, & x \notin <a> \\ f(x), & x \in <a> \end{array} \right. \),
reprezentând o partitie a lui \( \mathbb{N} \), de lungimi având cel mai mic multiplu comun \( n \). Reciproc, orice astfel de functie verifica trivial ipoteza.
Ca sa raspund la punctele a) si b), pentru \( n = 1 \), \( A_n = \{ \mathrm{Id}_{\mathbb{N}} \} \), iar daca \( n \ge 2 \), se observa ca \( A_n \) este nenumarabila.
PS. Bineinteles ca primele doua puncte sunt, în fapt, imediate construind o familie de solutii reiesind din ceea ce am scris mai sus.