Difference between revisions of "2007 AMC 12A Problems/Problem 25"
(solution, 1 by t0rajir0u and 2 by tarquin) |
(→Solution 1: fix table) |
||
Line 10: | Line 10: | ||
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>. | ||
− | The spacy subsets <math>S_{n + 1}</math> can be divided into | + | The spacy subsets <math>S_{n + 1}</math> can be divided into two subsets: |
+ | *Those containing <math>n + 1</math>. This is <math>S_{n - 2}</math>, since removing <math>n + 1</math> from any of these sets produces a spacy set with [[maximum|maximal]] element <math>n - 2</math>. | ||
+ | *Those not containing <math>n + 1</math>. This is <math>S_{n}</math>. | ||
+ | Hence, | ||
<div style="text-align:center;"><math>S_{n + 1} = S_{n} + S_{n - 2}</math></div> | <div style="text-align:center;"><math>S_{n + 1} = S_{n} + S_{n - 2}</math></div> | ||
− | From this recursion, we find that | + | From this [[recursion]], we find that |
− | {| class="wikitable" | + | {| class="wikitable" border="1px solid" |
|- | |- | ||
− | | S(1) || S(2) || S(3) || S(4) || S(5) || S(6) || S(7) || S(8) || S(9) || S(10) || S(11) || S(12) || | + | | <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 |
Revision as of 19:06, 20 September 2007
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
Solution 1
Let denote the number of spacy subsets of
. We have
.
The spacy subsets can be divided into two subsets:
- Those containing
. This is
, since removing
from any of these sets produces a spacy set with maximal element
.
- Those not containing
. This is
.
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 |
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
As a last resort, we can brute force the result by repeated casework. Luckily, 12 is not a very large number, so solving it this way is still possible.
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 |