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$

Solución:

Nota que debe haber al menos un $0$ para satisfacer la condición. Podemos proceder por casos según el número de dígitos distintos en la cadena.

$1$ dígito

El único dígito posible es $0.$ Esto se puede hacer de $1$ manera.

$2$ dígitos

Esto nos da un total de $20 + 30 + 20 + 5 = 75$ cadenas.

$3$ dígitos

Esto nos da un total de $120 + 150 + 90 + 60 + 60$ $+ 20 = 500$ cadenas.

$4$ dígitos

Esto nos da un total de $10 \cdot \dfrac{5!}{2! \cdot 1! \cdot 1! \cdot 1!} = 600$ cadenas.

$5$ dígitos

Esto nos da $5! = 120$ cadenas.

En total, tenemos $1 + 75 + 500 + 600$ $+ 120 = 1296$ cadenas.

Por lo tanto, E es la respuesta correcta.

Note that there must be at least one $0$ to satisfy the condition. We can proceed by casework on the number of distinct digits in the string.

$1$ digit

The only possible digit is just $0.$ This can be done in $1$ way.

$2$ digits

This gives us a total of $20 + 30 + 20 + 5 = 75$ strings.

$3$ digits

This gives us a total of $120 + 150 + 90 + 60 + 60$ $+ 20 = 500$ strings.

$4$ digits

This gives us a total of $10 \cdot \dfrac{5!}{2! \cdot 1! \cdot 1! \cdot 1!} = 600$ strings.

$5$ digits

This gives us $5! = 120$ strings.

All together, we have $1 + 75 + 500 + 600$ $+ 120 = 1296$ strings.

Thus, E is the correct answer.

2022 AMC 10A Problema 24

Solución:

El Problema 24 en otros años