Question

Halla el número de funciones $f(x)$ de $\{1, 2, 3, 4, 5\}$ a $\{1, 2, 3, 4, 5\}$ que satisfacen $f(f(x)) = f(f(f(x)))$ para todo $x$ en $\{1, 2, 3, 4, 5\}.$

Find the number of functions $f(x)$ from $\{1, 2, 3, 4, 5\}$ to $\{1, 2, 3, 4, 5\}$ that satisfy $f(f(x)) = f(f(f(x)))$ for all $x$ in $\{1, 2, 3, 4, 5\}.$

Respuesta

Solución:

Aplicar $f$ repetidamente a $f(f(x)) = f(f(f(x)))$ muestra que la condición significa que $f(f(x))$ es un punto fijo de $f$ para todo $x.$ Así que los elementos se organizan en niveles: un conjunto no vacío de $i$ puntos fijos, luego $j$ elementos cuya imagen es un punto fijo (pero que no son fijos), y los $5 - i - j$ elementos restantes, cada uno de los cuales debe aplicarse a uno de los $j$ elementos intermedios.

Para $i$ y $j$ dados hay $\binom{5}{i}$ formas de elegir los puntos fijos, $\binom{5-i}{j}$ formas de elegir el nivel intermedio, $i^j$ aplicaciones del nivel intermedio a los puntos fijos, y $j^{\,5-i-j}$ aplicaciones para el resto. Sumar $\binom{5}{i}\binom{5-i}{j}\, i^j \, j^{\,5-i-j}$ sobre los pares válidos (todos con $i \ge 1,$ $j \ge 1,$ más el caso identidad $i = 5$ ) da $\begin{aligned} &20 + 120 + 60 + 5 \\ &\quad {}+ 60 + 240 + 80 \\ &\quad {}+ 60 + 90 + 20 + 1 = 756. \end{aligned}$

Applying $f$ to $f(f(x)) = f(f(f(x)))$ repeatedly shows the condition means that $f(f(x))$ is a fixed point of $f$ for every $x.$ So the elements organize into levels: a nonempty set of $i$ fixed points, then $j$ elements whose image is a fixed point (but which are not fixed), and the remaining $5 - i - j$ elements, each of which must map to one of the $j$ middle elements.

For given $i$ and $j$ there are $\binom{5}{i}$ choices of fixed points, $\binom{5-i}{j}$ choices of the middle level, $i^j$ maps from the middle level to the fixed points, and $j^{\,5-i-j}$ maps for the rest. Summing $\binom{5}{i}\binom{5-i}{j}\, i^j \, j^{\,5-i-j}$ over the valid pairs (all $i \ge 1,$ $j \ge 1,$ plus the identity case $i = 5$ ) gives $\begin{aligned} &20 + 120 + 60 + 5 \\ &\quad {}+ 60 + 240 + 80 \\ &\quad {}+ 60 + 90 + 20 + 1 = 756. \end{aligned}$

2018 AIME II Problema 10

Solución:

El Problema 10 en otros años