Question

Halle el número de funciones $\pi$ que son sobreyectivas del conjunto $A = \{1, 2, 3, 4, 5, 6\}$ sobre $A$ y 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

Respuesta: 396

Conceptos:permutaciones conteo complementario análisis por casos

Nivel de dificultad: 2510

Pista pequeña:

Una aplicación sobreyectiva de un conjunto finito en sí mismo es una permutación, y la condición dice que su sexta potencia es la identidad

An onto map from a finite set to itself is a permutation, and the condition says its sixth power is the identity

Pista grande:

Equivalentemente, toda longitud de ciclo divide a $6,$ así que reste de $720$ las permutaciones que contienen un $4$ -ciclo o un $5$ -ciclo

Equivalently every cycle length divides $6,$ so subtract from $720$ the permutations that contain a $4$ -cycle or a $5$ -cycle

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 las permutaciones que contienen un $4$ -ciclo o un $5$ -ciclo del total $6! = 720.$ 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

Respuesta: 396

Nivel de dificultad: 2510

Pista pequeña:

Pista grande:

Solución:

El Problema 7 en otros años