2012 AMC 12B Problema 18

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.