2012 AMC 12B Problems/Problem 18

Problem 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$

Solution 1

Let $1\leq k\leq 10$ . Assume that $a_1=k$ . If $k<10$ , the first number appear after $k$ that is greater than $k$ must be $k+1$ , otherwise if it is any number $x$ larger than $k+1$ , there will be neither $x-1$ nor $x+1$ appearing before $x$ . Similarly, one can conclude that if $k+1<10$ , the first number appear after $k+1$ that is larger than $k+1$ must be $k+2$ , and so forth.

On the other hand, if $k>1$ , the first number appear after $k$ that is less than $k$ must be $k-1$ , and then $k-2$ , and so forth.

To count the number of possibilities when $a_1=k$ is given, we set up $9$ spots after $k$ , and assign $k-1$ of them to the numbers less than $k$ and the rest to the numbers greater than $k$ . The number of ways in doing so is $9$ choose $k-1$ .

Therefore, when summing up the cases from $k=1$ to $10$ , we get

$\binom{9}{0} + \binom{9}{1} + \cdots + \binom{9}{9} = 2^9=512 ...... \framebox{B}$

Solution 2

This problem is worded awkwardly. More simply, it asks: “How many ways can you order numbers 1-10 so that each term greater than 1 is one above or below some previous term?”

Then, the method becomes clear. For some initial number, WLOG examine the numbers greater than it. They always must appear in ascending order later in the list, only separated by the other numbers below it. Then, for some initial number, the number of possible lists is just the number of combination where this number of terms can be placed in 9 slots. For 9, that’s 1 number in 9 potential slots. For 8, that’s 2 numbers in 9 potential slots.

$\binom{9}{0} + \binom{9}{1} + \cdots + \binom{9}{9} =512 ... \boxed{B}$

~~BJHHar

Solution 3 (Noticing Stuff)

If there is only 1 number, the number of ways to order would be 1. If there are 2 numbers, the number of ways to order would be 2. If there are 3 numbers, by listing out, the number of ways is 4. We can then make a conjecture that the problem is simply powers of 2.

2012 AMC 12B (Problems • Answer Key • Resources)
Preceded by Problem 17	Followed by Problem 19
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 12 Problems and Solutions

Page

Toolbox

Search

2012 AMC 12B Problems/Problem 18

Contents

Problem 18

Solution 1

Solution 2

Solution 3 (Noticing Stuff)

See Also