Difference between revisions of "2007 AMC 12A Problems/Problem 25"
m (→Solution 1) |
|||
Line 18: | Line 18: | ||
{| class="wikitable" border="1px solid" | {| class="wikitable" border="1px solid" | ||
|- | |- | ||
− | | <math>S(0)</math> || <math>S(1)</math> || <math>S(2)</math> || <math>S(3)</math> || <math>S(4)</math> || <math>S(5)</math> || <math>S(6)</math> || <math>S(7)</math> || <math>S(8)</math> || <math>S(9)</math> || <math>S(10)</math> || <math>S(11)</math> || <math>S(12)</math> | + | | <math>S(0)</math> || <math>S(1)</math> || <math>S(2)</math> || <math>S(3)</math> || <math>S(4)</math> || <math>S(5)</math> || <math>S(6)</math> || <math>S(7)</math> || <math>S(8)</math> || <math>S(9)</math> || <math>S(10)</math> || <math>S(11)</math> || <math>S(12)</math> | |
|- | |- | ||
| 1 || 2 || 3 || 4 || 6 || 9 || 13 || 19 || 28 || 41 || 60 || 88 || 129 | | 1 || 2 || 3 || 4 || 6 || 9 || 13 || 19 || 28 || 41 || 60 || 88 || 129 | ||
− | + | } | |
And so the answer is <math>(E)</math> <math>129</math>. | And so the answer is <math>(E)</math> <math>129</math>. | ||
Revision as of 19:56, 19 June 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 2Since each of the elements of the subsets must be spaced at least two apart, a divider counting argument can be used. From the set For subsets of size Therefore, the number of spacy subsets is Solution 3A shifting argument is also possible, and is similar in spirit to Solution 2. Clearly we can have at most In general, the number of subsets of a set with Solution 4 (Casework)Let us consider each size of subset individually. Since each integer in the subset must be at least First, it is clear that there is Now, let us consider the spacy subsets with For spacy subsets with Lastly, there are Adding these all up, we have a total of See Also
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. |