Question

Sea $(a_1, a_2, \ldots, a_{10})$ una lista de los primeros $10$ enteros positivos tal que para cada $2 \le i \le 10$ o bien $a_i + 1$ o $a_i - 1$ o ambos aparecen en algún lugar antes de $a_i$ en la lista. ¿Cuántas listas de este tipo hay?

Let $(a_1, a_2, \ldots, a_{10})$ be a list of the first $10$ positive integers such that for each $2 \le i \le 10$ either $a_i + 1$ or $a_i - 1$ or both appear somewhere before $a_i$ in the list. How many such lists are there?

$120$

$512$

$1024$

$181{,}440$

$362{,}880$

Respuesta: B

Conceptos:biyección combinaciones

Nivel de dificultad: 1990

Pista pequeña:

Los números mayores o iguales que $a_1$ deben aparecer en orden creciente, y los menores que $a_1$ en orden decreciente

The numbers greater than or equal to $a_1$ must appear in increasing order, and those less than $a_1$ in decreasing order

Pista grande:

Elegir qué posiciones contienen los números pequeños determina la lista, lo que da $\sum_k \binom{9}{k}$

Choosing which positions hold the small numbers determines the list, giving $\sum_k \binom{9}{k}$

Solución:

Una vez fijado $a_1=k$ , los números $k,k+1,\ldots,10$ deben aparecer de izquierda a derecha en orden creciente, y los números $1,\ldots,k-1$ deben aparecer de derecha a izquierda en orden creciente (para que cada nuevo número pequeño tenga su sucesor ya colocado).

Para cada $k,$ la lista queda determinada al elegir cuáles de las $9$ posiciones después de la primera contienen los números menores que $k,$ lo que da $\binom{9}{k-1}$ listas.

Sumando, $\begin{aligned} \sum_{k=1}^{10}\binom{9}{k-1} &= \sum_{j=0}^{9}\binom{9}{j} \\ &= 2^9=512. \end{aligned}$

Por lo tanto, la respuesta correcta es B.

Once $a_1=k$ is fixed, the numbers $k,k+1,\ldots,10$ must appear left to right in increasing order, and the numbers $1,\ldots,k-1$ must appear from right to left in increasing order (so each new small number has its successor already placed).

For each $k,$ the list is determined by choosing which of the $9$ positions after the first hold the numbers below $k,$ giving $\binom{9}{k-1}$ lists.

Summing, $\begin{aligned} \sum_{k=1}^{10}\binom{9}{k-1} &= \sum_{j=0}^{9}\binom{9}{j} \\ &= 2^9=512. \end{aligned}$

Thus, the correct answer is B.

2012 AMC 12B Problema 18

Respuesta: B

Nivel de dificultad: 1990

Pista pequeña:

Pista grande:

Solución:

El Problema 18 en otros años