2007 AMC 12A Problema 25

Question

Llamamos espaciado a un conjunto de enteros si contiene no más de uno de cada tres enteros consecutivos. ¿Cuántos subconjuntos de

\{1,2,3,\ldots,12\},

incluido el conjunto vacío, son espaciados?

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

Respuesta: E

Conceptos:conteo recursivo subconjuntos

Nivel de dificultad: 2240

Pista pequeña:

Sea

c_n

el número de subconjuntos espaciados de

\{1,\ldots,n\}

; condiciona según si

n

está incluido.

Let

c_n

count the spacy subsets of

\{1,\ldots,n\}

; condition on whether

n

is included

Pista grande:

Excluir

n

da

c_{n-1}

; incluirlo prohíbe

n-1,n-2,

dando

c_{n-3},

así que

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

.

Excluding

n

gives

c_{n-1}

; including it forbids

n-1,n-2,

giving

c_{n-3},

so

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

Solución:

Sea

c_n

el número de subconjuntos espaciados de

\{1,\ldots,n\}.

Un subconjunto espaciado o bien omite

n

(hay

c_{n-1}

de estos) o bien contiene

n,

en cuyo caso omite

n-1

y

n-2

(hay

c_{n-3}

de estos).

Por lo tanto

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

con

c_1=2,

c_2=3,

c_3=4.

La sucesión continúa

6,9,13,19,28,41,60,88,129,

así que

c_{12}=129.

Por lo tanto, la respuesta correcta es E.

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.