Komentarz

XXXV OM - III - Zadanie 1

Wyznaczyć liczbę takich funkcji $ f $ odwzorowujących zbiór $ n $-elementowy w ten sam zbiór, że $ f^{n-1} $ jest funkcją stałą, zaś $ f^{n-2} $ nie jest funkcją stałą, gdzie $ f^k = f\circ f \circ \ldots \circ f $, $ n $ jest ustaloną liczbą naturalną większą od 2.

Rozwiązanie

Przypuśćmy, że $ A = \{a_1, a_2,\ldots, a_n \} $ jest danym zbiorem $ n $-efementowym, $ f $- funkcją spełniającą warunki zadania. Rozważmy zbiory $ A, f(A), f^2(A), \ldots, f^{n-1}(A) $. Z założenia wynika, że zbiór $ f^{n-1}(A) $ jest jednoelementowy, natomiast zbiór $ f^{n-2}(A) $ ma więcej niż jeden element. Ponadto $ f^{k-1}(A) \supset f^k(A) $ dla $ k = 1,2,\ldots,n - 1 $, gdyż każdy element postaci $ f^k(x) $ jest postaci $ f^{k-1}(y) $, gdzie $ y =f(x) $, a przy tym $ f^{k-1}(A) \ne f^k(A) $. Gdyby bowiem $ f^{k-1}(A) = f^k(A) = \{a_{i_1}, a_{i_2}, \ldots, a_{i_r}\} $, to funkcja $ f $ przekształcałaby podzbiór $ \{a_{i_1}, a_{i_2}, \ldots, a_{i_r}\} $ na ten sam podzbiór i byłaby na tym podzbiorze różnowartościowa. Każda iteracja funkcji $ f $ byłaby więc różnowartościowa na tym podzbiorze, wbrew temu, że $ f^{n-1} $ jest funkcją stałą.

Wobec tego mają miejsce zawierania

\[<br /> (*) \qquad A \supset f(A) \supset f^2(A) \supset \ldots \supset f^{n-2}(A) \supset f^{n-1}(A),<br /> \]

z których żadne nie jest równością. Zbiór $ A $ ma $ n $ elementów, zbiór $ f^{n-1}(A) $ ma jeden element. Wynika stąd, że każdy zbiór w ciągu (*) ma o jeden element mniej od zbioru poprzedniego.

Wykazaliśmy, że każda funkcja $ f $ spełniająca warunki zadania wyznacza ciąg podzbiorów zbioru $ A $, w którym każdy następny podzbiór powstaje z poprzedniego przez odrzucenie jednego elementu, a zatem jednoznacznie wyznacza pewną permutację zbioru $ A $.

Z drugiej strony każdy taki ciąg podzbiorów zbioru $ A $ jednoznacznie wyznacza funkcję $ f $ bo jeśli

\[<br /> f^{n-1}(A) = \{a_1\},\<br /> f^{n-2}(A) = \{a_1, a_2\},\<br /> f^{n-3}(A) = \{a_1, a_2, a_3\},\<br /> \ldots,<br /> \]
\[<br /> \ldots, f(A) = \{a_1, a_2, \ldots, a_{n-1}\},<br /> \]

to

\[<br /> f(a_1)=a_1, f(a_2)=a_1, f(a_3)=a_2, \ldots, f(a_n)=a_{n-1}.<br /> \]

Funkcje spełniające warunki zadania są wobec tego wyznaczone jednoznacznie przes permutacje zbioru $ A $. Ich liczba wynosi zatem $ n! $.

  • Wersja do wydrukuWersja do wydruku
  • Podziel się / Zapisz

Dodaj komentarz