Question

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?

$121$

$123$

$125$

$127$

$129$

Answer: E

Concepts:recursive counting subsets

Difficulty rating: 2240

Solution:

Let $c_n$ be the number of spacy subsets of $\{1,\ldots,n\}.$ A spacy subset either omits $n$ (there are $c_{n-1}$ of these) or contains $n,$ in which case it omits $n-1$ and $n-2$ (there are $c_{n-3}$ of these).

Hence $c_n=c_{n-1}+c_{n-3},$ with $c_1=2,$ $c_2=3,$ $c_3=4.$

The sequence continues $6,9,13,19,28,41,60,88,129,$ so $c_{12}=129.$

Thus, the correct answer is E.

2007 AMC 12A Problem 25

Answer: E

Difficulty rating: 2240

Solution:

Problem 25 in Other Years