# Mathematical Food for Thought

Serves a Daily Special and an All-You-Can-Eat Course in Problem Solving. Courtesy of me, Jeffrey Wang.

• ## Meta

Spacy. Topic: S&S/Sets. Level: AMC. February 7th, 2007

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 ?

### One Response to “Spacy. Topic: S&S/Sets. Level: AMC.”

1. t0rajir0u Says:

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