Sample Question 18:

Let \((a_1,a_2, \dots ,a_{10})\) be a list of the first \(10\) positive integers such that for each \(2 \le i \le 10\) either \(a_i+1\) or \(a_i-1\) or both appear somewhere before \(a_i\) in the list. How many such lists are there?

\(\textbf{(A)}\ 120\qquad\textbf{(B)}\ 512\qquad\textbf{(C)}\ 1024\qquad\textbf{(D)}\ 181,440\qquad\textbf{(E)}\ 362,880\)

---

Answer Keys

Question 18: B

---

Solutions

Question 18
Step 1: Assume that \(a_1=k\) where \(1\leq k\leq 10\).

Step 2: If \(k<10\), the first number that appears after \(k\) and is greater than \(k\) must be \(k+1\). If it is any number \(x\) larger than \(k+1\), neither \(x-1\) nor \(x+1\) will appear before \(x\).

Step 3: Similarly, if \(k+1<10\), the first number that appears after \(k+1\) and is larger than \(k+1\) must be \(k+2\), and so on.

Step 4: If \(k>1\), the first number that appears after \(k\) and is less than \(k\) must be \(k-1\), then \(k-2\), and so forth.

Step 5: To count the possibilities when \(a_1=k\) is given, we create 9 slots after \(k\), and assign \(k-1\) of them to numbers less than \(k\) and the rest to numbers greater than \(k\). The number of ways this can be done is \(\binom{9}{k-1}\).

Step 6: Summing up these cases for \(k\) from 1 to 10, we get:

\(\binom{9}{0} + \binom{9}{1} + \cdots + \binom{9}{9} = 2^9=512\)

Hence, the answer is \(\boxed{\textbf{(B) } 512}\).