2007 AMC 12A Problem 25

Problem 25 of 25HarderCombinatorics

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?

Show solution

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,

c_{12}=129.

Thus, the correct answer is E.

Tagged: recursive counting · subsets