Question

Halle el número de funciones $\pi$ que aplican el conjunto $A = \{1, 2, 3, 4, 5, 6\}$ sobre $A$ tales que para todo $a \in A,$ $\pi(\pi(\pi(\pi(\pi(\pi(a)))))) = a.$

Find the number of functions $\pi$ mapping the set $A = \{1, 2, 3, 4, 5, 6\}$ onto $A$ such that for every $a \in A,$ $\pi(\pi(\pi(\pi(\pi(\pi(a)))))) = a.$

Respuesta

Solución:

Una función de un conjunto finito sobre sí mismo es una biyección, así que $\pi$ es una permutación de seis elementos, y la condición dice que $\pi^6$ es la identidad. Una permutación satisface $\pi^6 = \mathrm{id}$ exactamente cuando todo ciclo de su descomposición en ciclos tiene longitud que divide a $6.$ Entre las longitudes posibles $1$ a $6,$ solo $4$ y $5$ no dividen a $6.$

Restamos de $6! = 720$ las permutaciones que contienen un $4$ -ciclo o un $5$ -ciclo. El tipo de ciclo $4+1+1$ da $\frac{6!}{4 \cdot 2!} = 90,$ el tipo $4+2$ da $\frac{6!}{4 \cdot 2} = 90,$ y el tipo $5+1$ da $\frac{6!}{5} = 144,$ para $90 + 90 + 144 = 324$ permutaciones excluidas.

El total es $720 - 324 = 396.$

A function from a finite set onto itself is a bijection, so $\pi$ is a permutation of six elements, and the condition says $\pi^6$ is the identity. A permutation satisfies $\pi^6 = \mathrm{id}$ exactly when every cycle in its cycle decomposition has length dividing $6.$ Among the possible lengths $1$ through $6,$ only $4$ and $5$ fail to divide $6.$

We subtract the permutations containing a $4$ -cycle or a $5$ -cycle from $6! = 720.$ Cycle type $4+1+1$ gives $\frac{6!}{4 \cdot 2!} = 90,$ type $4+2$ gives $\frac{6!}{4 \cdot 2} = 90,$ and type $5+1$ gives $\frac{6!}{5} = 144,$ for $90 + 90 + 144 = 324$ excluded permutations.

The count is $720 - 324 = 396.$

2026 AIME I Problema 7

Solución:

El Problema 7 en otros años