Question

求 $\{1, 2, 3, \ldots, 10\}$ 的子集个数，使得子集中恰好有一对连续整数。这样的子集例子包括 $\{\mathbf{1}, \mathbf{2}, 5\}$ 和 $\{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\}.$

答案

答案：235

知识点：子集斐波那契数列分类讨论

难度评级：2650

解答：

首先，一个由 $m$ 个连续整数组成的区块中，不含两个连续元素的子集个数是斐波那契数 $F_{m+2}$ （其中 $F_1 = F_2 = 1$ ）：按最后一个元素是否被选来分类，会得到斐波那契递推，初始计数为 $1, 2, 3, 5, \ldots$ 。

设唯一的连续整数对是 $\{k, k+1\}$ ，其中 $1 \le k \le 9$ 。其余元素必须排除 $k - 1$ 和 $k + 2$ （否则会产生第二对连续整数），并且在 $\{1, \ldots, k-2\}$ 与 $\{k+3, \ldots, 10\}$ ，这两个大小分别为 $k - 2$ 和 $8 - k$ 的区块中，不能包含连续整数。因此对此 $k$ 的计数为 $F_k \cdot F_{10-k}$ 。

对 $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 第 11 题

答案：235

难度评级：2650

解答：

其他年份的第 11 题