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

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 .

2012 AMC 10B Problem 22

Answer: B

Difficulty rating: 2060

Solution:

Problem 22 in Other Years