Question

Sea $(a_1,a_2,\ldots,a_{10})$ $2\le i\le10$ ... una lista de los primeros 10 enteros positivos tal que, para cada , $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\le10$ 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:arreglos con restricciones conteo recursivo trabajar hacia atrás

Nivel de dificultad: 2060

Solución:

Cada prefijo $a_1,a_2,\ldots,a_i$ debe formar un intervalo de enteros consecutivos: cada término nuevo debe ser uno más o uno menos que algún término ya presente. En particular, el conjunto completo es el intervalo $[1,10].$

Leamos la lista al revés. En cada paso, el término eliminado debe ser el menor o el mayor entero del intervalo actual; eliminar un término interior dejaría ese término sin un predecesor adyacente en la lista original. Recíprocamente, toda sucesión de eliminaciones de extremos produce una lista válida. Hay dos opciones para cada uno de $a_{10},a_9,\ldots,a_2,$ y después $a_1$ queda determinado. Por lo tanto, hay $2^9=512$ listas.

Así, la respuesta correcta es B.

Every prefix $a_1,a_2,\ldots,a_i$ must form an interval of consecutive integers: each new term is required to be one more or one less than a term already present. In particular, the full set is the interval $[1,10].$

Read the list backward. At each step, the term removed must be either the smallest or the largest integer in the current interval; removing an interior term would leave that term with no adjacent predecessor in the forward list. Conversely, every sequence of endpoint removals produces a valid list. There are two choices for each of $a_{10},a_9,\ldots,a_2,$ after which $a_1$ is forced. Hence there are $2^9=512$ lists.

Thus, the correct answer is B .

2012 AMC 10B Problema 22

Respuesta: B

Nivel de dificultad: 2060

Solución:

El Problema 22 en otros años