L OM - II - Zadanie 5

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.

Komentarze

Dodaj nową odpowiedź