Question

Sea $A = \{1, 2, 3, 4, 5, 6, 7\},$ y sea $N$ el número de funciones $f$ del conjunto $A$ al conjunto $A$ tales que $f(f(x))$ es una función constante. Halla el residuo cuando $N$ se divide entre $1000.$

Let $A = \{1, 2, 3, 4, 5, 6, 7\},$ and let $N$ be the number of functions $f$ from set $A$ to set $A$ such that $f(f(x))$ is a constant function. Find the remainder when $N$ is divided by $1000.$

Respuesta

Solución:

Digamos que $f(f(x)) = a$ para todo $x,$ y sea $S = \{x : f(x) = a\}.$ Tomando cualquier $t \in S,$ obtenemos $a = f(f(t)) = f(a),$ así que $a \in S.$ Todo $x$ satisface $f(x) \in S$ (porque $f(f(x)) = a$ ), y si $x \notin S$ entonces $f(x) \ne a,$ así que $f$ mapea el complemento de $S$ en $S \setminus \{a\}.$ Recíprocamente, cualquier $f$ construida de esta manera funciona.

Si $|S| = k,$ elegimos la constante $a$ de $7$ maneras, los $k - 1$ elementos restantes de $S$ de $\binom{6}{k-1}$ maneras, y una imagen en $S \setminus \{a\}$ para cada uno de los otros $7 - k$ elementos de $(k-1)^{7-k}$ maneras. Por lo tanto $\begin{aligned} N &= \scriptsize 7\sum_{k=1}^{7} \binom{6}{k-1}(k-1)^{7-k} \\ &\scriptsize = 7\,(0 + 6 + 240 + 540 + 240 + 30 + 1) \\ &= 7 \cdot 1057 = 7399. \end{aligned}$

El residuo cuando $N$ se divide entre $1000$ es $399.$

Say $f(f(x)) = a$ for all $x,$ and let $S = \{x : f(x) = a\}.$ Picking any $t \in S,$ we get $a = f(f(t)) = f(a),$ so $a \in S.$ Every $x$ satisfies $f(x) \in S$ (because $f(f(x)) = a$ ), and if $x \notin S$ then $f(x) \ne a,$ so $f$ maps the complement of $S$ into $S \setminus \{a\}.$ Conversely, any $f$ built this way works.

If $|S| = k,$ we choose the constant $a$ in $7$ ways, the remaining $k - 1$ elements of $S$ in $\binom{6}{k-1}$ ways, and an image in $S \setminus \{a\}$ for each of the $7 - k$ other elements in $(k-1)^{7-k}$ ways. Hence $\begin{aligned} N &= \scriptsize 7\sum_{k=1}^{7} \binom{6}{k-1}(k-1)^{7-k} \\ &\scriptsize = 7\,(0 + 6 + 240 + 540 + 240 + 30 + 1) \\ &= 7 \cdot 1057 = 7399. \end{aligned}$

The remainder when $N$ is divided by $1000$ is $399.$

2013 AIME II Problema 11

Solución:

El Problema 11 en otros años