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\},其他元素必须避开 k1k-1k+2k+2,并且在左右两个剩余区块内不相邻。

If the pair is {k,k+1},\{k, k+1\}, the other elements must avoid k1k-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\},其中 1k91 \le k \le 9。其余元素必须排除 k1k - 1k+2k + 2(否则会产生第二对连续整数),并且在 {1,,k2}\{1, \ldots, k-2\}{k+3,,10}\{k+3, \ldots, 10\},这两个大小分别为 k2k - 28k8 - k 的区块中,不能包含连续整数。因此对此 kk 的计数为 FkF10kF_k \cdot F_{10-k}

k=1,,9k = 1, \ldots, 9 求和:k=19FkF10k=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 1k9.1 \le k \le 9. The remaining elements must exclude k1k - 1 and k+2k + 2 (either would create a second consecutive pair) and must contain no consecutive pair within {1,,k2}\{1, \ldots, k-2\} or within {k+3,,10},\{k+3, \ldots, 10\}, blocks of sizes k2k - 2 and 8k.8 - k. So the count for this kk is FkF10k.F_k \cdot F_{10-k}.

Summing over k=1,,9:k = 1, \ldots, 9: k=19FkF10k=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 题