L OM - II - Zadanie 5

Zawody matematyczne:

L OM, 1998-1999

Etap:

Niech $S = \{1, 2,3,4, 5\}$ . Wyznaczyć liczbę funkcji $f: S \to S$ spełniających równość $f^{50} (x) = x$ dla wszystkich $x \in S$ .

Uwaga: $f^{50}(x) = \underbrace{f \circ f \circ \ldots \circ f}_{50} (x)$ .

Rozwiązanie

Niech $f$ będzie funkcją spełniającą warunki zadania. Dla liczb $x \neq y$ dostajemy $f^{49}(f(x)) = x \neq y = f^{49}(f(y))$ , skąd $f(x)\neq f(y)$ . Zatem $f$ jest permutacją zbioru $S$ . Oznaczmy przez $r(x)$ ( $x \in S$ ) najmniejszą liczbę całkowitą dodatnią taką, że $f^{r(x)}(x)= x$ . Wówczas $r(x) \leq 5$ oraz $r(x)|50$ , skąd $r(x)\in\{1,2,5\}$ .

Jeżeli istnieje taka liczba $a \in S$ , że $r(a)=5$ , to liczby $a$ , $f(a)$ , $f^2(a)$ , $f^3(a)$ , $f^4(a)$ są różne; wyczerpują więc zbiór $S$ . Wtedy dla dowolnej liczby $x\in S$ , $r(x)=5$ . Funkcja $f$ jest więc jednoznacznie wyznaczona przez permutację $(f(1),f^2(1),f^3(1),f^4(1))$ zbioru $\{2,3,4,5\}$ ; zatem może być określona na $4! =24$ sposoby.

Jeżeli dla wszystkich $x \in S$ zachodzi $r(x)=1$ , to $f$ jest funkcją identycznościową. Taka funkcja jest jedna.

Pozostał do rozpatrzenia przypadek, w którym największa wartość osiągana przez funkcję $r$ wynosi $2$ . Niech więc $a$ będzie takim elementem zbioru $S$ , że $r(a) = 2$ . Wtedy także $r(b) = 2$ , gdzie $b = f(a)$ .

Jeżeli $r(x) = 1$ dla wszystkich $x \in S \setminus \{a,b\}$ , to $f$ jest wyznaczona przez wybór dwuelementowego podzbioru $\{a,b\}$ zbioru $S$ , co można uczynić na ${5 \choose 2}=10$ sposobów.

Jeżeli natomiast istnieje taka liczba $c \in S \setminus \{a,b\}$ , że $r(c) = 2$ , to przyjmując $d=f(c)$ oraz oznaczając przez $e$ jedyny element zbioru $S\setminus \{a,b,c,d\}$ , mamy

$<br /> (1) \qquad f(a)= b,\ f(b)= a,\ f(c)= d,\ f(d)= c,\ f(e)= e.<br />$

Taka funkcja $f$ jest wyznaczona przez wybór liczby $e$ (można to zrobić na $5$ sposobów) oraz podział zbioru $S \setminus \{e\}$ na dwa podzbiory dwuelementowe $\{a,b\}$ i $\{c,d\}$ (istnieją $3$ takie podziały). Dostajemy więc $15$ funkcji postaci (1).

Łącznie istnieje $50$ funkcji spełniających warunki zadania.