Question

¿Cuántas cadenas de longitud $5$ formadas con los dígitos $0,$ $1,$ $2,$ $3,$ $4$ hay tales que para cada $j\in\{1,2,3,4\},$ al menos $j$ de los dígitos son menores que $j$ ? (Por ejemplo, $02214$ satisface la condición porque contiene al menos $1$ dígito menor que $1,$ al menos $2$ dígitos menores que $2,$ al menos $3$ dígitos menores que $3,$ y al menos $4$ dígitos menores que $4.$ La cadena $23404$ no satisface la condición porque no contiene al menos $2$ dígitos menores que $2.$ )

How many strings of length $5$ formed from the digits $0,$ $1,$ $2,$ $3,$ $4$ are there such that for each $j\in\{1,2,3,4\},$ at least $j$ of the digits are less than $j?$ (For example, $02214$ satisfies the condition because it contains at least $1$ digit less than $1,$ at least $2$ digits less than $2,$ at least $3$ digits less than $3,$ and at least $4$ digits less than $4.$ The string $23404$ does not satisfy the condition because it does not contain at least $2$ digits less than $2.$ )

$500$

$625$

$1089$

$1199$

$1296$

Respuesta: E

Conceptos:arreglos con restricciones análisis por casos

Nivel de dificultad: 2380

Pista pequeña:

“Al menos $j$ dígitos son menores que $j$ ” significa que el $j$ -ésimo dígito más pequeño es a lo sumo $j-1$

“At least $j$ digits are less than $j$ ” means the $j$ th smallest digit is at most $j-1$

Pista grande:

Estas son funciones de estacionamiento de longitud $5;$ usa el conteo de estacionamiento circular con $6$ lugares

These are parking functions of length $5;$ use the circular-parking count with $6$ spaces

Solución:

Ordenemos los cinco dígitos como $d_{(1)}\le d_{(2)}\le\cdots\le d_{(5)}.$ El requisito “al menos $j$ dígitos menores que $j$ ” equivale a $d_{(j)}\le j-1$ para $j=1,2,3,4,$ es decir, $d_{(1)}=0,\ d_{(2)}\le1,$ $\ d_{(3)}\le2,\ d_{(4)}\le3$ (con $d_{(5)}\le4$ automático).

Estas cadenas son exactamente las funciones de estacionamiento de longitud $5.$ Para contarlas, dispongamos $6$ lugares de estacionamiento en un círculo y hagamos que $5$ autos etiquetados elijan lugares preferidos arbitrarios. Cada auto avanza hasta el primer lugar libre. Entre las $6^5$ cadenas de preferencias, rotar todas las preferencias hace que el único lugar vacío recorra las $6$ posiciones. Por tanto, exactamente $\frac{6^5}{6}=6^4=1296$ cadenas dejan vacío un lugar especificado. Elegirlo como el sexto lugar extra produce precisamente las desigualdades ordenadas anteriores.

Por lo tanto, la respuesta correcta es E.

Sort the five digits as $d_{(1)}\le d_{(2)}\le\cdots\le d_{(5)}.$ The requirement “at least $j$ digits less than $j$ ” is equivalent to $d_{(j)}\le j-1$ for $j=1,2,3,4,$ i.e. $d_{(1)}=0,\ d_{(2)}\le1,$ $\ d_{(3)}\le2,\ d_{(4)}\le3$ (with $d_{(5)}\le4$ automatic).

These strings are exactly the parking functions of length $5.$ To count them, arrange $6$ parking spaces in a circle and let $5$ labeled cars choose arbitrary preferred spaces. Each car moves forward to the first open space. Among the $6^5$ preference strings, rotating all preferences cycles the unique empty space through all $6$ positions. Therefore exactly $\frac{6^5}{6}=6^4=1296$ strings leave a specified space empty. Choosing that space as the extra sixth space gives precisely the sorted inequalities above.

Thus, the correct answer is E.

2022 AMC 12A Problema 24

Respuesta: E

Nivel de dificultad: 2380

Pista pequeña:

Pista grande:

Solución:

El Problema 24 en otros años