Problem: (2007 AMC 12A – #25) 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: We will solve this problem with a recursion on , which we will define as the number of spacy subsets of . We can easily calculate
, , , and .
Now we will think about how to evaluate in terms of previous terms. Obviously, we can keep all the subsets in . These will account for any space subsets that don’t contain the element . Now we just need to count the ones that do contain the element .
If a spacy subset contains , it cannot have or . So take all the spacy subsets of and add the element to them to get all the spacy subsets that contain . Since these are both of the cases, we obtain
Some calculations yield . QED.
Comment: In all honesty, a pretty standard recursion problem, which is probably better off on an easy olympiad-style contest because it’s too easy to guess on the AMC. After just calculating a few terms, it wasn’t hard to see the recursion and assume its validity. A more interesting problem would be to find the closed form for that recursion (eww?). Maybe generating functions will save the day.
Practice Problem: Can you find a closed form for ?
Leave a Reply
You must be logged in to post a comment.