2012 AMC 12B Problem 18

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

The numbers greater than or equal to

a_1

must appear in increasing order, and those less than

a_1

in decreasing order

Choosing which positions hold the small numbers determines the list, giving

\sum_k \binom{9}{k}

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.

Problem 18 in other years