Question

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$

Solution:

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, $\sum_{k=1}^{10}\binom{9}{k-1}=\sum_{j=0}^{9}\binom{9}{j}=2^9=512.$

Thus, the correct answer is B.

2012 AMC 12B Problem 18

Solution:

Problem 18 in Other Years