XXXV OM - III - Zadanie 1

Zawody matematyczne:

XXXV OM, 1983-1984

Etap:

III

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

$ (*) \qquad A \supset f(A) \supset f^2(A) \supset \ldots \supset f^{n-2}(A) \supset f^{n-1}(A), $

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

$ f^{n-1}(A) = \{a_1\},\ f^{n-2}(A) = \{a_1, a_2\},\ f^{n-3}(A) = \{a_1, a_2, a_3\},\ \ldots, $