2007 AMC 12A Problems/Problem 25
Contents
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,
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
Solution 5
We build a modified version of Markov's chain to solve this problem. First, start off by representing each element of the chosen subset with a , and every other element . The possible states are as follows; if the restriction was broken previously or not. For the sake of not over counting, we let the former be its own state (call it "C"), and the latter will be split up into more states. The previous two digits can either be , , or . If a previous digit doesn't exist, it is for obvious reasons. We know that we start off at state "". We have two options; include the first digit () or not (). Thus, state transitions to state in case and state in case. State transitions to in case and the "C" state in case. State transitions to in case and state "C" in case. Since it doesn't matter where or how many times the restriction is broken for the subset to fail, state "C" can transition to itself in cases.
Notice how this corresponds to a transition matrix of . Since we start off on state , our starting state matrix is . We wish to compute the value when given , where is Through repeated applications of matrix multiplication, we obtain the output matrix of . Our answer is thus . Remark: Markov's Chain is more commonly used to calculate probabilities, but it also can be very useful for counting problems with a uniform requirement. -SigmaPiE
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.