2012 AMC 10B Problem 22

1. Try a small case. Use the numbers $1, 2, 3$. Check all six orders:
- $123$, $213$, $231$, $321$ work;
- $132$ fails ($3$ comes second, but neither $2$ nor $4$ is before it);
- $312$ fails ($1$ comes second, but $2$ is not before it).
So there are $4$ lists.
2. What the rule really says. Look at the numbers written so far. At the start there is one number, a "run" of consecutive numbers of length $1$. Each new number must be $1$ more or $1$ less than something already written, and it can't repeat a number. So it must be just below the smallest number so far or just above the largest. Either way the numbers written so far are still a run of consecutive numbers, like $4, 5, 6, 7$.
3. Read the list backward. All ten numbers form the run $1, \ldots, 10$. The first nine must also form a run, so the last number $a_{10}$ must be an end: $1$ or $10$. That is $2$ choices.
4. Take $a_{10}$ away. The remaining nine numbers are a run, and $a_9$ must be one of its two ends: $2$ choices again.
5. This keeps going for $a_{10}, a_9, \ldots, a_2$: nine numbers, each with $2$ choices. At the end one number is left, and it has to be $a_1$.
6. Total:
$$2^9 = 512.$$

This matches the small case: with $3$ numbers there are $2^2 = 4$ lists.

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

The rule only talks about neighbors, but it has a big effect: the numbers used so far are always a solid run. Counting backward makes every step look the same (always $2$ ends to choose from). Counting forward, the number of choices changes once the run hits $1$ or $10$, which makes the count messy. When a count is awkward in one direction, try the other.

Build the pattern from small cases: $1$ number gives $1$ list, $2$ numbers give $2$ lists ($12$ and $21$), $3$ numbers give $4$ lists. Doubling each time suggests $2^9 = 512$ for $10$ numbers, and $512$ is one of the choices. The backward argument above shows why the doubling always continues.