Question

Halla el número de subconjuntos de $\{1, 2, 3, \ldots, 10\}$ que contienen exactamente un par de enteros consecutivos. Ejemplos de tales subconjuntos son $\{\mathbf{1}, \mathbf{2}, 5\}$ y $\{1, 3, \mathbf{6}, \mathbf{7}, 10\}.$

Find the number of subsets of $\{1, 2, 3, \ldots, 10\}$ that contain exactly one pair of consecutive integers. Examples of such subsets are $\{\mathbf{1}, \mathbf{2}, 5\}$ and $\{1, 3, \mathbf{6}, \mathbf{7}, 10\}.$

Respuesta

Solución:

Primero, el número de subconjuntos de un bloque de $m$ enteros consecutivos que no contienen dos elementos consecutivos es el número de Fibonacci $F_{m+2}$ (con $F_1 = F_2 = 1$ ): condicionar según si el último elemento se usa da la recursión de Fibonacci, y los conteos empiezan $1, 2, 3, 5, \ldots$

Supón que el único par consecutivo es $\{k, k+1\}$ para algún $1 \le k \le 9.$ Los elementos restantes deben excluir $k - 1$ y $k + 2$ (cualquiera de ellos crearía un segundo par consecutivo) y no deben contener ningún par consecutivo dentro de $\{1, \ldots, k-2\}$ ni dentro de $\{k+3, \ldots, 10\},$ bloques de tamaños $k - 2$ y $8 - k.$ Así que el conteo para este $k$ es $F_k \cdot F_{10-k}.$

Sumando sobre $k = 1, \ldots, 9:$ $\begin{aligned} \sum_{k=1}^{9} F_k F_{10-k} &= 34 + 21 + 26 \\ &\quad {}+ 24 + 25 + 24 \\ &\quad {}+ 26 + 21 + 34 \\ &= 235. \end{aligned}$

First, the number of subsets of a block of $m$ consecutive integers containing no two consecutive elements is the Fibonacci number $F_{m+2}$ (with $F_1 = F_2 = 1$ ): conditioning on whether the last element is used gives the Fibonacci recursion, and the counts start $1, 2, 3, 5, \ldots$

Suppose the unique consecutive pair is $\{k, k+1\}$ for some $1 \le k \le 9.$ The remaining elements must exclude $k - 1$ and $k + 2$ (either would create a second consecutive pair) and must contain no consecutive pair within $\{1, \ldots, k-2\}$ or within $\{k+3, \ldots, 10\},$ blocks of sizes $k - 2$ and $8 - k.$ So the count for this $k$ is $F_k \cdot F_{10-k}.$

Summing over $k = 1, \ldots, 9:$ $\begin{aligned} \sum_{k=1}^{9} F_k F_{10-k} &= 34 + 21 + 26 \\ &\quad {}+ 24 + 25 + 24 \\ &\quad {}+ 26 + 21 + 34 \\ &= 235. \end{aligned}$

2023 AIME I Problema 11

Solución:

El Problema 11 en otros años