Spacy. Topic: S&S/Sets. Level: AMC.

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 $ \{1, 2, 3, \ldots, 12\} $, including the empty set, are spacy?

Solution: We will solve this problem with a recursion on $ S_n $, which we will define as the number of spacy subsets of $ \{1, 2, 3, \ldots, n\} $. We can easily calculate

$ S_0 = 1 $, $ S_1 = 2 $, $ S_2 = 3 $, and $ S_3 = 4 $.

Now we will think about how to evaluate $ S_n $ in terms of previous terms. Obviously, we can keep all the subsets in $ S_{n-1} $. These will account for any space subsets that don't contain the element $ n $. Now we just need to count the ones that do contain the element $ n $.

If a spacy subset contains $ n $, it cannot have $ n-1 $ or $ n-2 $. So take all the spacy subsets of $ \{1, 2, \ldots, n-3\} $ and add the element $ n $ to them to get all the spacy subsets that contain $ n $. Since these are both of the cases, we obtain

$ S_n = S_{n-1}+S_{n-3} $.

Some calculations yield $ S_{12} = 129 $. 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 $ S_n $?