2007 AMC 12A Problem 25

Attempt Problem 25 of the 2007 AMC 12A below, then check your answer against the professionally curated solution from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2007 AMC 12A solutions, or check the answer key.

All problems are used with official legal permission of the Mathematical Association of America (MAA).

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?

121

123

125

127

129

Let

c_n

count the spacy subsets of

\{1,\ldots,n\}

; condition on whether

n

is included

Excluding

n

gives

c_{n-1}

; including it forbids

n-1,n-2,

giving

c_{n-3},

c_n=c_{n-1}+c_{n-3}

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.

Problem 25 in other years