2023 AIME I 第 11 题

先试着解答 2023 AIME I 第 11 题,然后核对你的答案与精心整理的解答,解答来自 LIVE by Po-Shen Loh。你也可以参加完整限时模拟考试、查看全部 2023 AIME I 解答,或核对答案。

所有题目均经美国数学协会(MAA)官方合法授权使用。

11.

求 {1,2,3,…,10}\{1, 2, 3, \ldots, 10\} 的子集个数,使得子集中恰好有一对连续整数。这样的子集例子包括 {1,2,5}\{\mathbf{1}, \mathbf{2}, 5\} 和 {1,3,6,7,10}\{1, 3, \mathbf{6}, \mathbf{7}, 10\}。

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

答案:235
知识点:子集斐波那契数列分类讨论
难度评级:2650
小提示:

从 mm 个连续整数中选子集且不含相邻元素的个数,是斐波那契数 Fm+2F_{m+2}。

The number of subsets of mm consecutive integers with no two consecutive elements is the Fibonacci number Fm+2.F_{m+2}.

大提示:

若这对连续整数是 {k,k+1}\{k, k+1\},其他元素必须避开 k−1k-1 和 k+2k+2,并且在左右两个剩余区块内不相邻。

If the pair is {k,k+1},\{k, k+1\}, the other elements must avoid k−1k-1 and k+2k+2 and be non-consecutive inside the two remaining blocks.

解答:

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

设唯一的连续整数对是 {k,k+1}\{k, k+1\},其中 1≤k≤91 \le k \le 9。其余元素必须排除 k−1k - 1 和 k+2k + 2(否则会产生第二对连续整数),并且在 {1,…,k−2}\{1, \ldots, k-2\} 与 {k+3,…,10}\{k+3, \ldots, 10\},这两个大小分别为 k−2k - 2 和 8−k8 - k 的区块中,不能包含连续整数。因此对此 kk 的计数为 Fk⋅F10−kF_k \cdot F_{10-k}。

对 k=1,…,9k = 1, \ldots, 9 求和:∑k=19FkF10−k=34+21+26+24+25+24+26+21+34=235。 \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}\text{。}

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

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

Summing over k=1,…,9:k = 1, \ldots, 9: ∑k=19FkF10−k=34+21+26+24+25+24+26+21+34=235. \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}

第 10 题#10
完整试卷

其他年份的第 11 题