2012 AMC 10B Problem 22

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\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

Answer: B

Concepts:arrangements with restrictions recursive counting work backwards

Difficulty rating: 2060

Small hint:

At each reverse step, remove either the smallest or largest remaining number

Big hint:

There are

2

choices until the final number is forced

Solution:

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 .