Question

Let $(a_1,$ $a_2,$ ... $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$

Solution:

Suppose we have $a_1.$ Then we can either add $a_1-1$ or $a_1+1.$ Then, when every we add some number, we must have it in a connected interval to the numbers before.

Thus, our last interval would be $[1,10].$ If we construct a list backwards, we need to take either the lowest or highest numbers in the list. We can do this $9$ times to get $a_{10},$ then $a_9$ and continually until we get $a_2.$ Then, $a_1$ is given. For each index, we choose an upper or lower, so there are $2$ choices. Thus, the total is $2^9=512.$

Thus, the correct answer is B .

2012 AMC 10B Problem 22

Solution:

Problem 22 in Other Years