Difference between revisions of "2007 AMC 12A Problems/Problem 25"
Vishnuemani (talk | contribs) (→Problem) |
(→Solution) |
||
Line 38: | Line 38: | ||
In general, the number of subsets of a set with <math>n</math> element and with no <math>k</math> consecutive numbers is <math>\sum^{\lfloor{\frac{n}{k}}\rfloor}_{i=0}{{n-(k-1)(i-1) \choose i}}</math>. | In general, the number of subsets of a set with <math>n</math> element and with no <math>k</math> consecutive numbers is <math>\sum^{\lfloor{\frac{n}{k}}\rfloor}_{i=0}{{n-(k-1)(i-1) \choose i}}</math>. | ||
+ | |||
+ | Solution 4 | ||
+ | |||
+ | For each positive integer <math>n</math>, let <math>S_n = \{k:1\leq k\leq | ||
+ | n\}</math>, and let <math>c_n</math> be the number of spacy subsets of <math>S_n</math>. Then <math>c_1=2</math>, <math>c_2=3</math>, and <math>c_3=4</math>. For <math>n\geq 4</math>, the spacy subsets of <math>S_n</math> can be partitioned into two types: those that contain <math>n</math> and those that do not. Those that do not contain <math>n</math> are precisely the spacy subsets of <math>S_{n-1}</math>. Those that contain <math>n</math> do not contain either <math>n-1</math> or <math>n-2</math> and are therefore in one-to-one correspondence with the spacy subsets of <math>S_{n-3}</math>. It follows that <math>c_n=c_{n-3}+c_{n-1}</math>. Thus the first twelve terms in the sequence <math>\left(c_n\right)</math> are <math>2</math>, <math>3</math>, <math>4</math>, <math>6</math>, <math>9</math>, <math>13</math>, <math>19</math>, <math>28</math>, <math>41</math>, <math>60</math>, <math>88</math>, <math>129</math>, and there are <math>c_{12}=\boxed{129}</math> spacy subsets of <math>S_{12}</math>. | ||
== See also == | == See also == |
Revision as of 15:27, 5 April 2016
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 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 |
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 similiar 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 element and with no
consecutive numbers is
.
Solution 4
For each positive integer , let
, and let
be the number of spacy subsets of
. Then
,
, and
. For
, the spacy subsets of
can be partitioned into two types: those that contain
and those that do not. Those that do not contain
are precisely the spacy subsets of
. Those that contain
do not contain either
or
and are therefore in one-to-one correspondence with the spacy subsets of
. It follows that
. Thus the first twelve terms in the sequence
are
,
,
,
,
,
,
,
,
,
,
,
, and there are
spacy subsets of
.
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.