Difference between revisions of "2012 AMC 10B Problems/Problem 22"
(→Solution 2) |
(→Problem) |
||
(26 intermediate revisions by 12 users not shown) | |||
Line 1: | Line 1: | ||
==Problem== | ==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? | ||
− | |||
<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> | ||
Line 8: | Line 7: | ||
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 | + | 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 16: | Line 15: | ||
<math>\dbinom{9}{0} +\dbinom{9}{1} + \dbinom{9}{2} + \dbinom{9}{3} + \dbinom{9}{4}.....\dbinom{9}{9}</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>\boxed{\textbf{(B)}}</math> | + | By the [[binomial theorem]], this is <math>2^{9}</math> = <math>512</math>, or <math>\boxed{\textbf{(B)}}</math> |
==Solution 2== | ==Solution 2== | ||
Line 25: | Line 24: | ||
==Solution 3== | ==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> | + | 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{(B) }512}</math>. | ||
+ | |||
+ | - ColtsFan10 | ||
+ | |||
+ | ==Solution 5== | ||
+ | Solution 3 states that <math>f(n)=2^{n-1} ~\forall~ n \ge 1</math> without formal proof. Solution 4 gives a formal proof. Here is another formal proof: | ||
+ | |||
+ | <math>f(1)=1</math>. When the list goes from <math>n-1</math> numbers to <math>n</math> numbers, there are <math>2</math> ways to make the new lists: | ||
+ | |||
+ | Case 1: append <math>n</math> to the end of lists with <math>n-1</math> numbers to make a new list, the number of the new lists is <math>f(n-1)</math>; | ||
+ | |||
+ | Case 2: put number <math>1</math> at the end of the new lists, the way to arrange <math>(2,3,...,n-1,n)</math> as the first <math>n-1</math> items is the same as to arrange <math>(1,2,...,n-2,n-1)</math>, by subtracting 1 from each of the elements, so the number of the new lists is also <math>f(n-1)</math>. | ||
+ | |||
+ | So <math>f(n)=f(n-1)+f(n-1)=2f(n-1)=2^{n-1} ~\forall~ n \ge 1</math> | ||
+ | |||
+ | -[https://artofproblemsolving.com/wiki/index.php/User:Junche junche] | ||
+ | |||
+ | ==Video Solution by Richard Rusczyk== | ||
+ | https://artofproblemsolving.com/videos/amc/2012amc10b/269 | ||
+ | |||
+ | ~dolphin7 | ||
+ | |||
+ | ==Video Solution by TheBeautyofMath== | ||
+ | https://youtu.be/bXPSv93GVbg | ||
+ | |||
+ | ~IceMatrix | ||
== See Also == | == See Also == |
Latest revision as of 10:19, 21 April 2024
Contents
Problem
Let (, , ... ) be a list of the first 10 positive integers such that for each either or or both appear somewhere before in the list. How many such lists are there?
Solution 1
If we have 1 as the first number, then the only possible list is .
If we have 2 as the first number, then we have 9 ways to choose where the goes, and the numbers ascend from the first number, , with the exception of the . For example, , or . There are 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 ways to do this.
In the same way, the total number of lists is:
By the binomial theorem, this is = , or
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 . There are 9 arrows, so the answer is =
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, and . If we replace it with 3, there are four lists, and . Since 2 and 4 are both powers of 2, it is likely that the number of lists is , where is the length of the lists.
Solution 4 (Recursion)
If , the sequence must be . If , then , and the sequence is . If , then the possible sequences are In general, for an -length sequence, if , then through can be filled in ways with through , and through must be sorted in decreasing order with the remaining numbers ( through ), in one way. Thus , where .
We can see (or prove by induction) that . Hence, .
- ColtsFan10
Solution 5
Solution 3 states that without formal proof. Solution 4 gives a formal proof. Here is another formal proof:
. When the list goes from numbers to numbers, there are ways to make the new lists:
Case 1: append to the end of lists with numbers to make a new list, the number of the new lists is ;
Case 2: put number at the end of the new lists, the way to arrange as the first items is the same as to arrange , by subtracting 1 from each of the elements, so the number of the new lists is also .
So
Video Solution by Richard Rusczyk
https://artofproblemsolving.com/videos/amc/2012amc10b/269
~dolphin7
Video Solution by TheBeautyofMath
~IceMatrix
See Also
2012 AMC 10B (Problems • Answer Key • Resources) | ||
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.