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

Respuesta: 756

Conceptos:función combinaciones análisis por casos

Nivel de dificultad: 3060

Pista pequeña:

La condición dice que todo valor de $f \circ f$ es un punto fijo de $f.$ Clasifica los elementos según cuántas aplicaciones de $f$ necesitan para llegar a un punto fijo.

The condition says every value of $f \circ f$ is a fixed point of $f.$ Classify elements by how many applications of $f$ they need to reach a fixed point.

Pista grande:

Con $i$ puntos fijos y $j$ elementos más que se envían directamente a ellos, los $5 - i - j$ elementos restantes deben tener su imagen entre esos $j;$ cuenta cada caso con coeficientes binomiales

With $i$ fixed points and $j$ further elements mapping straight to them, the remaining $5 - i - j$ elements must map to those $j;$ count each case with binomial coefficients

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$ formas de enviar el nivel intermedio a los puntos fijos, y $j^{\,5-i-j}$ formas de asignar las imágenes del 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

Respuesta: 756

Nivel de dificultad: 3060

Pista pequeña:

Pista grande:

Solución:

El Problema 10 en otros años