## Wednesday, February 7, 2007

### 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$?

#### 1 comment:

1. Cardano's method or whatever it's called on x^3 = x + 1 to find the roots. Ewww.