Olimpiadas de Matemáticas
Página de preparación y problemas
Competiciones
| OME Local |
| OME Andaluza |
| OME Nacional |
| OIM |
| IMO |
| EGMO |
| USAMO |
| ASU |
| OMCC |
| Retos UJA |
Buscar problemas
La base de datos contiene 2434 problemas y 940 soluciones.
Problema 1149
Sea $A=\{1,2,3,4,5,6\}$.
- ¿Cuantas funciones $f:A\to A$ verifican $f(f(x))=x$ para todo $x\in A$?
- ¿Cuantas funciones $f:A\to A$ verifican $f(f(f(x)))=x$ para todo $x\in A$?
pistasolución 1info
Pista. En ambos casos las funciones tienen que ser biyectivas, es decir, tienen que representar permutaciones de los elementos de $A$. Aparte de los elementos que se quedan fijos, en el apartado (a) aparecerán parejas de elementos de $A$ que se intercambien, mientras que en (b) habrá tríos que se intercambien cíclicamente.
Solución.
- La función $f$ tiene que ser biyectiva ya que $f^{-1}=f$ ($f$ es su propia inversa), lo que nos dice que $f$ permuta los valores del conjunto $A$. Además, como $f(f(x))=x$, la función actúa sobre parejas de elementos de $A$ intercambiando sus valores o bien dejando elementos de $A$ fijos. Habrá tantas funciones $f$ como formas extraer parejas disjuntas de $A=\{1,2,3,4,5,6\}$:
- Con cero parejas hay una forma de hacerlo (dejar todo fijo).
- Con una pareja hay $\binom{6}{2}=15$ formas de hacerlo.
- Con dos parejas hay $\frac{1}{2}\binom{6}{2}\binom{4}{2}=\frac{1}{2}\cdot 15\cdot 6=45$ formas de hacerlo. El razonamiento para obtener esta fórmula es que hay $\binom{6}{2}$ formas de elegir la primera pareja y $\binom{4}{2}$ formas para la segunda (quedan sólo 4 elementos para elegir), pero estamos contando cada configuración dos veces.
- Con tres parejas hay $\frac{1}{6}\binom{6}{2}\binom{4}{2}\binom{2}{2}=\frac{1}{6}\cdot 15\cdot 6\cdot 1=15$ formas de hacerlo. El razonamiento es similar al anterior, pero estamos contado cada configuración $3!=6$ veces.
- El razonamiento para este apartado es similar. Observamos que $f$ también es biyectiva ya que cumple $f^{-1}=f\circ f$. Ahora bien, al cumplirse que $f(f(f(x)))=x$ para todo $x\in A$, se sigue que $f$ permuta cíclicamente tríos de elementos de $A$ y deja otros fijos. Ahora bien, cada trío $\{x,y,z\}$ tiene dos posibles permutaciones cíclicas según el orden en que se roten los elementos, que son $x\mapsto y\mapsto z\mapsto x$ y $x\mapsto z\mapsto y\mapsto x$. Tenemos tres casos:
- Con cero tríos hay una forma de hacerlo (dejar todo fijo).
- Con un trío hay $\binom{6}{3}=20$ formas de elegir el trío, lo que nos da 20\cdot 2=40$ posibles permutaciones.
- Con dos tríos hay $\frac{1}{2}\binom{6}{3}\binom{3}{3}=10$ formas de elegir los dos tríos, lo que nos da $10\cdot 4=40$ posibles permutaciones (hay que elegir el orden de rotación en cada trío).
Tenemos así un total de $1+40+40=81$ funciones que cumplen este apartado.
Si crees que el enunciado contiene un error o imprecisión o bien crees que la información sobre la procedencia del problema es incorrecta, puedes notificarlo usando los siguientes botones:
Informar de error en enunciado Informar de procedencia del problema
Informar de error en enunciado Informar de procedencia del problema
José Miguel Manzano © 2010-2025. Esta página ha sido creada mediante software libre