Question

¿Cuántos subconjuntos no vacíos $S$ de $\{1, 2, 3, \ldots, 15\}$ tienen las siguientes dos propiedades?

$(1)$ Ningún par de enteros consecutivos pertenece a $S.$

$(2)$ Si $S$ contiene $k$ elementos, entonces $S$ no contiene ningún número menor que $k.$

How many non-empty subsets $S$ of $\{1, 2, 3, \ldots, 15\}$ have the following two properties?

$(1)$ No two consecutive integers belong to $S.$

$(2)$ If $S$ contains $k$ elements, then $S$ contains no number less than $k.$

$277$

$311$

$376$

$377$

$405$

Solución:

Por la propiedad $(2),$ un conjunto válido de $k$ elementos es un $k$ -subconjunto de $\{k, k+1, \ldots, 15\}$ sin dos elementos consecutivos.

Al colapsar los huecos entre los elementos elegidos, estos corresponden biyectivamente a los $k$ -subconjuntos de un conjunto de $(17 - 2k)$ elementos, contados por $\binom{17 - 2k}{k}.$ Esto es distinto de cero solo para $k \le 5,$ así que el total es $\begin{gathered} \binom{15}{1} + \binom{13}{2} \\ {}+ \binom{11}{3} + \binom{9}{4} \\ {}+ \binom{7}{5} \\ = 15 + 78 + 165 + 126 + 21 \\ = 405. \end{gathered}$

Por lo tanto, la respuesta correcta es E.

By property $(2),$ a valid $k$ -element set is a $k$ -subset of $\{k, k+1, \ldots, 15\}$ with no two consecutive elements.

Collapsing the gaps between chosen elements, these correspond bijectively to $k$ -subsets of a $(17 - 2k)$ -element set, counted by $\binom{17 - 2k}{k}.$ This is nonzero only for $k \le 5,$ so the total is $\begin{gathered} \binom{15}{1} + \binom{13}{2} \\ {}+ \binom{11}{3} + \binom{9}{4} \\ {}+ \binom{7}{5} \\ = 15 + 78 + 165 + 126 + 21 \\ = 405. \end{gathered}$

Thus, the correct answer is E.

2006 AMC 12A Problema 25

Solución:

El Problema 25 en otros años