Difference between revisions of "2007 AMC 12A Problems/Problem 25"
m (minor edit) |
|||
Line 4: | Line 4: | ||
<math>\mathrm{(A)}\ 121 \qquad \mathrm{(B)}\ 123 \qquad \mathrm{(C)}\ 125 \qquad \mathrm{(D)}\ 127 \qquad \mathrm{(E)}\ 129</math> | <math>\mathrm{(A)}\ 121 \qquad \mathrm{(B)}\ 123 \qquad \mathrm{(C)}\ 125 \qquad \mathrm{(D)}\ 127 \qquad \mathrm{(E)}\ 129</math> | ||
− | + | == Solution 1 == | |
− | |||
Let <math>S_{n}</math> denote the number of spacy subsets of <math>\{ 1, 2, ... n \}</math>. We have <math>S_{0} = 1, S_{1} = 2, S_{2} = 3</math>. | Let <math>S_{n}</math> denote the number of spacy subsets of <math>\{ 1, 2, ... n \}</math>. We have <math>S_{0} = 1, S_{1} = 2, S_{2} = 3</math>. | ||
Line 25: | Line 24: | ||
And so the answer is <math>(E)</math> <math>129</math>. | And so the answer is <math>(E)</math> <math>129</math>. | ||
− | + | == Solution 2 == | |
Since each of the elements of the subsets must be spaced at least two apart, a divider counting argument can be used. | Since each of the elements of the subsets must be spaced at least two apart, a divider counting argument can be used. | ||
Line 34: | Line 33: | ||
Therefore, the number of spacy subsets is <math>\binom 64 + \binom 83 + \binom{10}2 + \binom{12}1 + \binom{14}0 = \boxed{129} </math>. | Therefore, the number of spacy subsets is <math>\binom 64 + \binom 83 + \binom{10}2 + \binom{12}1 + \binom{14}0 = \boxed{129} </math>. | ||
− | + | == Solution 3 == | |
A shifting argument is also possible, and is similar in spirit to Solution 2. Clearly we can have at most <math>4</math> elements. Given any arrangment, we subract <math>2i-2</math> from the <math>i-th</math> element in our subset, when the elements are arranged in increasing order. This creates a [[bijection]] with the number of size <math>k</math> subsets of the set of the first <math>14-2k</math> positive integers. For instance, the arrangment o | | o | | o | | | o | corresponds to the arrangment o o o | o |. Notice that there is no longer any restriction on consectutive numbers. Therefore, we can easily plug in the possible integers 0, 1, 2, 3, 4, 5 for <math>k</math>: <math>{14 \choose 0} + {12 \choose 1} + {10 \choose 2} + {8 \choose 3} + {6 \choose 4} = \boxed{129}</math> | A shifting argument is also possible, and is similar in spirit to Solution 2. Clearly we can have at most <math>4</math> elements. Given any arrangment, we subract <math>2i-2</math> from the <math>i-th</math> element in our subset, when the elements are arranged in increasing order. This creates a [[bijection]] with the number of size <math>k</math> subsets of the set of the first <math>14-2k</math> positive integers. For instance, the arrangment o | | o | | o | | | o | corresponds to the arrangment o o o | o |. Notice that there is no longer any restriction on consectutive numbers. Therefore, we can easily plug in the possible integers 0, 1, 2, 3, 4, 5 for <math>k</math>: <math>{14 \choose 0} + {12 \choose 1} + {10 \choose 2} + {8 \choose 3} + {6 \choose 4} = \boxed{129}</math> | ||
Revision as of 02:12, 16 February 2021
Problem
Call a set of integers spacy if it contains no more than one out of any three consecutive integers. How many subsets of including the empty set, are spacy?
Solution 1
Let denote the number of spacy subsets of
. We have
.
The spacy subsets of can be divided into two groups:
those not containing
. Clearly
.
those containing
. We have
, since removing
from any set in
produces a spacy set with all elements at most equal to
and each such spacy set can be constructed from exactly one spacy set in
.
Hence,
![$S_{n + 1} = S_{n} + S_{n - 2}$](http://latex.artofproblemsolving.com/6/7/c/67cef40285a255e1c2cdf97100c25e31affcf407.png)
From this recursion, we find that
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
|
1 | 2 | 3 | 4 | 6 | 9 | 13 | 19 | 28 | 41 | 60 | 88 | 129 |
And so the answer is
.
Solution 2
Since each of the elements of the subsets must be spaced at least two apart, a divider counting argument can be used.
From the set we choose at most four numbers. Let those numbers be represented by balls. Between each of the balls there are at least two dividers. So for example, o | | o | | o | | o | | represents
.
For subsets of size there must be
dividers between the balls, leaving
dividers to be be placed in
spots between the balls. The number of way this can be done is
.
Therefore, the number of spacy subsets is .
Solution 3
A shifting argument is also possible, and is similar in spirit to Solution 2. Clearly we can have at most elements. Given any arrangment, we subract
from the
element in our subset, when the elements are arranged in increasing order. This creates a bijection with the number of size
subsets of the set of the first
positive integers. For instance, the arrangment o | | o | | o | | | o | corresponds to the arrangment o o o | o |. Notice that there is no longer any restriction on consectutive numbers. Therefore, we can easily plug in the possible integers 0, 1, 2, 3, 4, 5 for
:
In general, the number of subsets of a set with elements and with no
consecutive numbers is
.
Solution 4 (Casework)
Let us consider each size of subset individually. Since each integer in the subset must be at least away from any other integer in the subset, the largest spacy subset contains
elements.
First, it is clear that there is spacy set with
elements in it, the empty set. Next, there are
spacy subsets with
element in them, one for each integer
through
.
Now, let us consider the spacy subsets with elements in them. If the smaller integer is
, the larger integer is any of the
integers from
to
. If the smaller integer is
, the larger integer is any of the
integers from
to
. This continues, up to a smaller integer of
and
choice for the larger integer,
. This means that there are
spacy subsets with
elements.
For spacy subsets with elements, we first consider the middle integer. The smallest such integer is
, and it allows for
possible value for the smaller integer (
) and possible
values for the larger integer (
through
), for a total of
possible subsets. The next middle integer,
, allows for
smaller integers and
larger integers, and this pattern continues up until the middle integer of
, which has
values for the smaller integer and
value for the larger integer. This means that there are
spacy subsets with
elements.
Lastly, there are main categories for spacy subsets with
elements, defined by the difference between their smallest and largest values. The difference ranges from
to
. If it is
, there is only
set of places to put the two middle values (
and
, where
is the smallest value). Since there are
possible sets of smallest and largest values, there are
sets in this category. If the difference is
, there are now
sets of places to put the two middle values (
and
or
, and
and
). There are
possible sets of smallest and largest values, so there are
sets in this category. Finally, if the difference is
, there are
possible sets of places to put the two middle values (
and
,
, or
,
and
or
, and
and
) and one possible set of smallest and largest values, meaning that there are
sets in this category. Adding them up, there are
spacy subsets with
elements.
Adding these all up, we have a total of spacy subsets. ~emerald_block
See Also
2007 AMC 12A (Problems • Answer Key • Resources) | |
Preceded by Problem 24 |
Followed by Last question |
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.