Difference between revisions of "2012 AMC 10B Problems/Problem 22"

(Problem 22)
m (Solution 4 (Recursion))
(28 intermediate revisions by 14 users not shown)
Line 1: Line 1:
==Problem 22==
+
==Problem==
 
Let (<math>a_1</math>, <math>a_2</math>, ... <math>a_{10}</math>) be a list of the first 10 positive integers such that for each <math>2\le</math> <math>i</math> <math>\le10</math> either <math>a_i + 1</math> or <math>a_i-1</math> or both appear somewhere before <math>a_i</math> in the list. How many such lists are there?
 
Let (<math>a_1</math>, <math>a_2</math>, ... <math>a_{10}</math>) be a list of the first 10 positive integers such that for each <math>2\le</math> <math>i</math> <math>\le10</math> either <math>a_i + 1</math> or <math>a_i-1</math> or both appear somewhere before <math>a_i</math> in the list. How many such lists are there?
  
Line 5: Line 5:
 
<math>\textbf{(A)}\ \ 120\qquad\textbf{(B)}\ 512\qquad\textbf{(C)}\ \ 1024\qquad\textbf{(D)}\ 181,440\qquad\textbf{(E)}\ \ 362,880</math>
 
<math>\textbf{(A)}\ \ 120\qquad\textbf{(B)}\ 512\qquad\textbf{(C)}\ \ 1024\qquad\textbf{(D)}\ 181,440\qquad\textbf{(E)}\ \ 362,880</math>
  
                                                                                                                            SOLUTION 1
+
==Solution 1==
 
If we have 1 as the first number, then the only possible list is <math>(1,2,3,4,5,6,7,8,9,10)</math>.  
 
If we have 1 as the first number, then the only possible list is <math>(1,2,3,4,5,6,7,8,9,10)</math>.  
  
If we have 2 as the first number, then we have 9 ways to choose where the one goes, and the numbers ascend from the first number, 2, with the exception of the 1.
+
If we have 2 as the first number, then we have 9 ways to choose where the <math>1</math> goes, and the numbers ascend from the first number, <math>2</math>, with the exception of the <math>1</math>.
 
For example, <math>(2,3,1,4,5,6,7,8,9,10)</math>, or <math>(2,3,4,1,5,6,7,8,9,10)</math>. There are <math>\dbinom{9}{1}</math> ways to do so.
 
For example, <math>(2,3,1,4,5,6,7,8,9,10)</math>, or <math>(2,3,4,1,5,6,7,8,9,10)</math>. There are <math>\dbinom{9}{1}</math> ways to do so.
  
Line 14: Line 14:
  
 
In the same way, the total number of lists is:
 
In the same way, the total number of lists is:
<math>\dbinom{9}{1} + \dbinom{9}{2} + \dbinom{9}{3} + \dbinom{9}{4}.....\dbinom{9}{10}</math>
+
<math>\dbinom{9}{0} +\dbinom{9}{1} + \dbinom{9}{2} + \dbinom{9}{3} + \dbinom{9}{4}.....\dbinom{9}{9}</math>
 
   
 
   
By the binomial theorem, this is <math>2^{9}</math> = <math>512</math>, or <math>(A)</math>  
+
By the binomial theorem, this is <math>2^{9}</math> = <math>512</math>, or <math>\boxed{\textbf{(B)}}</math>
  
+
==Solution 2==
                                                                                                                              SOLUTION 2
+
Arrange the spaces and put arrows pointing either up or down between them. Then for each arrangement of arrows there is one and only one list that corresponds to up. For example, all arrows pointing up is <math>(1,2,3,4,5...10)</math>. There are 9 arrows, so the answer is <math>2^{9}</math> = <math>512</math> <math>\boxed{\textbf{(B)}}</math>
Arrange the spaces and put arrows pointing either up or down between them. Then for each arrangement of arrows there is one and only one list that corresponds to up. For example, all arrows pointing up is <math>(1,2,3,4,5...10)</math>. There are 9 arrows, so the answer is <math>2^{9}</math> = <math>512</math>
+
 
 +
NOTE:
 +
Solution cited from: http://www.artofproblemsolving.com/Videos/external.php?video_id=269.
 +
 
 +
==Solution 3==
 +
Notice that the answer to the problem is solely based on the length of the lists, i.e. 10. We can replace 10 with smaller values, such as 2 and 3, and try to find a pattern. If we replace it with 2, we can easily see that there are two possible lists, <math>(1, 2)</math> and <math>(2, 1)</math>. If we replace it with 3, there are four lists, <math>(1, 2, 3), (2, 1, 3), (2, 3, 1),</math> and <math>(3, 2, 1)</math>. Since 2 and 4 are both powers of 2, it is likely that the number of lists is <math>2^{n-1}</math>, where <math>n</math> is the length of the lists. <math>2^{10-1}=512=\boxed{\textbf{(B)}}</math>
 +
 
 +
==Solution 4 (Recursion)==
 +
If <math>a_1=10</math>, the sequence must be <math>10, 9, 8,7,6,5,4,3,2,1</math>. If <math>a_2=10</math>, then <math>a_1=9</math>, and the sequence is <math>9, 10, 8, 7, 6, 5,4,3,2,1</math>. If <math>a_3=10</math>, then the possible sequences are <cmath>9,8,10,7,6,5,4,3,2,1 \text{ and}</cmath><cmath>8,9,10,7,6,5,4,3,2,1.</cmath> In general, for an <math>n</math>-length sequence, if <math>a_i=n</math>, then <math>a_1</math> through <math>a_{i-1}</math> can be filled in <math>f(i-1)</math> ways with <math>n-i+1</math> through <math>n-1</math>, and <math>a_{i+1}</math> through <math>a_{n}</math> must be sorted in decreasing order with the remaining numbers (<math>1</math> through <math>n-i</math>), in one way. Thus <math>f(n) = \sum_{i=0}^{n-1} f(i)</math>, where <math>f(0)=1</math>.
 +
 
 +
We can see (or prove by induction) that <math>f(n)=2^{n-1} ~\forall~ n \ge 1</math>. Hence, <math>f(10)=2^9=\boxed{\textbf{(D) }512}</math>.
 +
 
 +
- ColtsFan10
 +
 
 +
==Solution 5 ==
 +
Assume the same conditions to be held and let's look at several smaller cases to find a pattern. If we are only arranging <math>1,2</math> there are trivially only <math>2</math> ways. Now let us look at arranging <math>1,2,3</math>. You can arrange this in <math>4</math> ways. Looking at <math>1,2,3,4</math> you can arrange this in <math>8</math> ways. The pattern becomes evident now. If there are <math>n</math> numbers there are <math>2^{n-1}</math> ways. Hence our answer would be <math>2^{10-1} = 512</math> ways which is <math>\boxed{B}</math>.
 +
 
 +
-srisainandan6
 +
 
 +
==Video Solution by Richard Rusczyk==
 +
https://artofproblemsolving.com/videos/amc/2012amc10b/269
 +
 
 +
~dolphin7
 +
 
 +
==Video Solution==
 +
https://youtu.be/bXPSv93GVbg
 +
 
 +
~IceMatrix
 +
 
 +
== See Also ==
 +
 
 +
 
 +
{{AMC10 box|year=2012|ab=B|num-b=21|num-a=23}}
 +
{{MAA Notice}}

Revision as of 19:18, 16 December 2020

Problem

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?


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

Solution 1

If we have 1 as the first number, then the only possible list is $(1,2,3,4,5,6,7,8,9,10)$.

If we have 2 as the first number, then we have 9 ways to choose where the $1$ goes, and the numbers ascend from the first number, $2$, with the exception of the $1$. For example, $(2,3,1,4,5,6,7,8,9,10)$, or $(2,3,4,1,5,6,7,8,9,10)$. There are $\dbinom{9}{1}$ ways to do so.

If we use 3 as the first number, we need to choose 2 spaces to be 2 and 1, respectively. There are $\dbinom{9}{2}$ ways to do this.

In the same way, the total number of lists is: $\dbinom{9}{0} +\dbinom{9}{1} + \dbinom{9}{2} + \dbinom{9}{3} + \dbinom{9}{4}.....\dbinom{9}{9}$

By the binomial theorem, this is $2^{9}$ = $512$, or $\boxed{\textbf{(B)}}$

Solution 2

Arrange the spaces and put arrows pointing either up or down between them. Then for each arrangement of arrows there is one and only one list that corresponds to up. For example, all arrows pointing up is $(1,2,3,4,5...10)$. There are 9 arrows, so the answer is $2^{9}$ = $512$ $\boxed{\textbf{(B)}}$

NOTE: Solution cited from: http://www.artofproblemsolving.com/Videos/external.php?video_id=269.

Solution 3

Notice that the answer to the problem is solely based on the length of the lists, i.e. 10. We can replace 10 with smaller values, such as 2 and 3, and try to find a pattern. If we replace it with 2, we can easily see that there are two possible lists, $(1, 2)$ and $(2, 1)$. If we replace it with 3, there are four lists, $(1, 2, 3), (2, 1, 3), (2, 3, 1),$ and $(3, 2, 1)$. Since 2 and 4 are both powers of 2, it is likely that the number of lists is $2^{n-1}$, where $n$ is the length of the lists. $2^{10-1}=512=\boxed{\textbf{(B)}}$

Solution 4 (Recursion)

If $a_1=10$, the sequence must be $10, 9, 8,7,6,5,4,3,2,1$. If $a_2=10$, then $a_1=9$, and the sequence is $9, 10, 8, 7, 6, 5,4,3,2,1$. If $a_3=10$, then the possible sequences are \[9,8,10,7,6,5,4,3,2,1 \text{ and}\]\[8,9,10,7,6,5,4,3,2,1.\] In general, for an $n$-length sequence, if $a_i=n$, then $a_1$ through $a_{i-1}$ can be filled in $f(i-1)$ ways with $n-i+1$ through $n-1$, and $a_{i+1}$ through $a_{n}$ must be sorted in decreasing order with the remaining numbers ($1$ through $n-i$), in one way. Thus $f(n) = \sum_{i=0}^{n-1} f(i)$, where $f(0)=1$.

We can see (or prove by induction) that $f(n)=2^{n-1} ~\forall~ n \ge 1$. Hence, $f(10)=2^9=\boxed{\textbf{(D) }512}$.

- ColtsFan10

Solution 5

Assume the same conditions to be held and let's look at several smaller cases to find a pattern. If we are only arranging $1,2$ there are trivially only $2$ ways. Now let us look at arranging $1,2,3$. You can arrange this in $4$ ways. Looking at $1,2,3,4$ you can arrange this in $8$ ways. The pattern becomes evident now. If there are $n$ numbers there are $2^{n-1}$ ways. Hence our answer would be $2^{10-1} = 512$ ways which is $\boxed{B}$.

-srisainandan6

Video Solution by Richard Rusczyk

https://artofproblemsolving.com/videos/amc/2012amc10b/269

~dolphin7

Video Solution

https://youtu.be/bXPSv93GVbg

~IceMatrix

See Also

2012 AMC 10B (ProblemsAnswer KeyResources)
Preceded by
Problem 21
Followed by
Problem 23
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 10 Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png