Difference between revisions of "2012 AMC 12B Problems/Problem 18"
Isabelchen (talk | contribs) m (→Solution 5 (Recursion)) |
Isabelchen (talk | contribs) m (→Solution 5 (Recursion)) |
||
(One intermediate revision by the same user not shown) | |||
Line 45: | Line 45: | ||
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: | 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 | + | 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 | + | 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> | 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> |
Latest revision as of 00:50, 27 December 2022
Contents
Problem 18
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
Let . Assume that
. If
, the first number appear after
that is greater than
must be
, otherwise if it is any number
larger than
, there will be neither
nor
appearing before
. Similarly, one can conclude that if
, the first number appear after
that is larger than
must be
, and so forth.
On the other hand, if , the first number appear after
that is less than
must be
, and then
, and so forth.
To count the number of possibilities when is given, we set up
spots after
, and assign
of them to the numbers less than
and the rest to the numbers greater than
. The number of ways in doing so is
choose
.
Therefore, when summing up the cases from to
, we get
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.
~~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.
.
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 .
~BlueDragon
Solution 5 (Recursion)
For a list with
terms,
valid lists with
terms can be created by
ways:
1. Add to the end of the list, making a new list
2. Increase the value of all existing terms by one, making a new list . Then add
to the end of the list, making a new list
Let be the number of lists with
elements,
. As
,
,
Video Solution by Richard Rusczyk
https://artofproblemsolving.com/videos/amc/2012amc12b/269
~dolphin7
Video Solution by IceMatrix
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.