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 esta 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 this 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:parking functions circular counting arreglos con restricciones

Nivel de dificultad: 2390

Solución:

Consideremos los cinco dígitos, en orden, como los espacios preferidos de cinco autos. Los espacios están numerados $0,1,2,3,4,$ y cada auto ocupa su espacio preferido si está libre; de lo contrario, ocupa el primer espacio vacío a su derecha. Si las preferencias ordenadas son $b_1\le b_2\le\cdots\le b_5,$ todos los autos se estacionan exactamente cuando $b_i\le i-1\qquad(1\le i\le5).$ Estas desigualdades son precisamente las condiciones del problema.

Para contar, añadamos un sexto espacio y dispongamos los espacios $0,1,\ldots,5$ en un círculo. Para cualquiera de las $6^5$ cadenas de preferencias, los cinco autos se estacionan y queda exactamente un espacio vacío. Al rotar cada preferencia una posición, también rota el espacio vacío. Así, cada órbita de seis cadenas tiene exactamente una vez cada posible espacio vacío.

Por tanto, exactamente $6^5/6=6^4=1296$ cadenas circulares dejan vacío el espacio $5$ . Ningún auto de tal cadena prefiere el espacio $5,$ y al cortar el círculo justo después de ese espacio vacío obtenemos exactamente una sucesión exitosa en los espacios $0$ a $4.$ Así, el número pedido de cadenas es $1296.$

Por lo tanto, E es la respuesta correcta.

Regard the five digits, in order, as the preferred parking spaces of five cars. Spaces are numbered $0,1,2,3,4,$ and each car takes its preferred space if possible, or else the first empty space to its right. If the preferences sorted into nondecreasing order are $b_1\le b_2\le\cdots\le b_5,$ all cars park exactly when $b_i\le i-1\qquad(1\le i\le5).$ These inequalities are precisely the conditions in the problem.

To count such preference strings, add a sixth space and arrange spaces $0,1,\ldots,5$ in a circle. For any of the $6^5$ preference strings, all five cars park and exactly one space remains empty. Rotating every preference by one position rotates the empty space as well. Thus each orbit of six preference strings has each possible empty space exactly once.

Therefore exactly $6^5/6=6^4=1296$ circular preference strings leave space $5$ empty. No car in such a string prefers space $5,$ and cutting the circle immediately after that empty space gives exactly a successful parking sequence on spaces $0$ through $4.$ Hence the desired number of strings is $1296.$

Thus, E is the correct answer.

2022 AMC 10A Problema 24

Respuesta: E

Nivel de dificultad: 2390

Solución:

El Problema 24 en otros años