Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2012 AMC 12B Problems/Problem 18"

(Created page with "== Problem 18 == Let <math>(a_1,a_2, \dots ,a_{10})</math> be a list of the first 10 positive integers such that for each <math>2 \le i \le 10</math> either <math>a_i+1</math> o...")
 
m (→‎Solution 5 (Recursion))
 
(23 intermediate revisions by 11 users not shown)
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 ==
+
== Solution 1==
 
Let <math>1\leq k\leq 10</math>. Assume that <math>a_1=k</math>. If <math>k<10</math>, the first number appear after <math>k</math> that is greater than <math>k</math> must be <math>k+1</math>, otherwise if it is any number <math>x</math> larger than <math>k+1</math>, there will be neither <math>x-1</math> nor <math>x+1</math> appearing before <math>x</math>. Similarly, one can conclude that if <math>k+1<10</math>, the first number appear after <math>k+1</math> that is larger than <math>k+1</math> must be <math>k+2</math>, and so forth.
 
Let <math>1\leq k\leq 10</math>. Assume that <math>a_1=k</math>. If <math>k<10</math>, the first number appear after <math>k</math> that is greater than <math>k</math> must be <math>k+1</math>, otherwise if it is any number <math>x</math> larger than <math>k+1</math>, there will be neither <math>x-1</math> nor <math>x+1</math> appearing before <math>x</math>. Similarly, one can conclude that if <math>k+1<10</math>, the first number appear after <math>k+1</math> that is larger than <math>k+1</math> must be <math>k+2</math>, and so forth.
  
Line 15: Line 15:
  
 
<cmath>\binom{9}{0} + \binom{9}{1} + \cdots + \binom{9}{9} = 2^9=512 ...... \framebox{B}</cmath>
 
<cmath>\binom{9}{0} + \binom{9}{1} + \cdots + \binom{9}{9} = 2^9=512 ...... \framebox{B}</cmath>
 +
 +
== Solution 2==
 +
This problem is worded awkwardly. More simply, it asks: “How many ways can you order numbers 1-10 so that each number 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, though not necessarily as adjacent terms. 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.
 +
 +
<cmath>\binom{9}{0} + \binom{9}{1} + \cdots + \binom{9}{9} =512 \implies \boxed{B}</cmath>
 +
 +
~~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.
 +
<math>2^{10-1}=512</math>.
 +
 +
== Solution 4 (fast and clever)==
 +
Assume that the first element is any integer.
 +
Since we can only add the integer 1 more than the current max or 1 less the current min, there are 2 possibilities for each element after the first.
 +
Once we have created a set of 10 elements, we can shift all of the elements by some constant so that they will be the first 10 positive integers.
 +
Thus the total possibilities is <math>2^9</math>.
 +
 +
~BlueDragon
 +
 +
==Solution 5 (Recursion)==
 +
 +
For a list <math>{a_1, a_2, \dots, a_k}</math> with <math>k</math> terms, <math>2</math> valid lists with <math>k+1</math> terms can be created by <math>2</math> ways:
 +
 +
1. Add <math>a_{k+1}</math> to the end of the list, making a new list <math>{a_1, a_2, \dots, a_k, a_{k+1} }</math>
 +
 +
2. Increase the value of all existing terms by one, making a new list <math>{a_2, a_3, \dots, a_{k+1}}</math>. Then add <math>a_1</math> to the end of the list, making a new list <math>{a_2, a_3, \dots, a_{k+1}, a_1}</math>
 +
 +
Let <math>F(n)</math> be the number of lists with <math>n</math> elements, <math>F(n) = 2 \cdot F(n-1)</math>. As <math>F(2) = 2</math>, <math>F(n) = 2^{n-1}</math>, <math>F(10) = 2^9 = \boxed{\textbf{(B) } 512}</math>
 +
 +
~[https://artofproblemsolving.com/wiki/index.php/User:Isabelchen isabelchen]
 +
 +
==Video Solution by Richard Rusczyk==
 +
https://artofproblemsolving.com/videos/amc/2012amc12b/269
 +
 +
~dolphin7
 +
 +
==Video Solution by IceMatrix==
 +
https://youtu.be/bXPSv93GVbg
 +
 +
== See Also ==
 +
 +
{{AMC12 box|year=2012|ab=B|num-b=17|num-a=19}}
 +
 +
[[Category:Introductory Combinatorics Problems]]
 +
{{MAA Notice}}

Latest revision as of 23:50, 26 December 2022

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 number 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, though not necessarily as adjacent terms. 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 \implies \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. 

$2^{10-1}=512$.

Solution 4 (fast and clever)

Assume that the first element is any integer. Since we can only add the integer 1 more than the current max or 1 less the current min, there are 2 possibilities for each element after the first. Once we have created a set of 10 elements, we can shift all of the elements by some constant so that they will be the first 10 positive integers. Thus the total possibilities is $2^9$.

~BlueDragon

Solution 5 (Recursion)

For a list ${a_1, a_2, \dots, a_k}$ with $k$ terms, $2$ valid lists with $k+1$ terms can be created by $2$ ways:

1. Add $a_{k+1}$ to the end of the list, making a new list ${a_1, a_2, \dots, a_k, a_{k+1} }$

2. Increase the value of all existing terms by one, making a new list ${a_2, a_3, \dots, a_{k+1}}$. Then add $a_1$ to the end of the list, making a new list ${a_2, a_3, \dots, a_{k+1}, a_1}$

Let $F(n)$ be the number of lists with $n$ elements, $F(n) = 2 \cdot F(n-1)$. As $F(2) = 2$, $F(n) = 2^{n-1}$, $F(10) = 2^9 = \boxed{\textbf{(B) } 512}$

~isabelchen

Video Solution by Richard Rusczyk

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

~dolphin7

Video Solution by IceMatrix

https://youtu.be/bXPSv93GVbg

See Also

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

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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2012_AMC_12B_Problems/Problem_18&oldid=184974"