2012 AMC 10B Problem 22

The rule says every new entry is a neighbor of something already listed. So the set $\{a_1, \dots, a_i\}$ is always a block of consecutive integers: it starts as a single number, and attaching a neighbor to a block of consecutive integers produces a longer block. Conversely, any list in which each prefix is a block satisfies the rule, because a new number that extends a block is adjacent to the block's end.

Now count by reading the list backwards. The full set $\{1, \dots, 10\}$ is a block, and $a_{10}$ must be one of its two ends ($1$ or $10$), otherwise the first nine entries would not form a block. Removing $a_{10}$ leaves a block of nine numbers, and $a_9$ must be one of its two ends. This continues: each of $a_{10}, a_9, \dots, a_2$ is an end of the current block, giving $2$ choices each, and $a_1$ is whatever single number remains.

Total:
$$2^9 = 512.$$

The answer is $\boxed{\textbf{(B)}\ 512}$.

The condition is local ("adjacent to something earlier"), but its consequence is global: prefixes are intervals. Working backwards is what makes the count uniform, since the last element of an interval-building list is always an endpoint, while going forwards the number of options depends on whether the block has already hit $1$ or $10$. Look for a reformulation where every step has the same number of choices.

Small cases: with $\{1\}$ there is $1$ list; with $\{1,2\}$ there are $2$; with $\{1,2,3\}$ there are $4$ ($123, 213, 231, 321$). The pattern $2^{n-1}$ gives $2^9 = 512$ for $n = 10$, and $512$ is the only power of $2$ of that size among the choices.

• Counting forward by choosing a_1 and multiplying by 2 per step, which overcounts because once the block hits 1 or 10 only one direction remains.
• Answering $2^{10} = 1024$ by giving $a_1$ two choices as well; the last remaining number is forced.