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.

2007 AMC 12A Problema 25

Respuesta: E

Nivel de dificultad: 2240

Pista pequeña:

Pista grande:

Solución:

El Problema 25 en otros años