2015 AIME II 第 10 题

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

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

10.

若整数 11、22、…\ldots、nn 的一个排列 a1a_1、a2a_2、…\ldots、ana_n 满足对每个 1≤k≤n−11 \le k \le n - 1 都有 ak≤ak+1+2a_k \le a_{k+1} + 2,则称它为准递增排列。例如,5342153421 和 1425314253 是整数 11、22、33、44、55 的准递增排列,但 4512345123 不是。求整数 11、22、…\ldots、77 的准递增排列个数。
Call a permutation a1,a_1, a2,a_2, …,\ldots, ana_n of the integers 1,1, 2,2, …,\ldots, nn quasi-increasing if ak≤ak+1+2a_k \le a_{k+1} + 2 for each 1≤k≤n−1.1 \le k \le n - 1. For example, 5342153421 and 1425314253 are quasi-increasing permutations of the integers 1,1, 2,2, 3,3, 4,4, 5,5, but 4512345123 is not. Find the number of quasi-increasing permutations of the integers 1,1, 2,2, …,\ldots, 7.7.
答案:486
知识点:排列递推计数
难度评级:2890
小提示:
试着把 nn 插入一个 1,…,n−11, \ldots, n-1 的准递增排列中,从而构造 1,…,n1, \ldots, n 的准递增排列
Try building a quasi-increasing permutation of 1,…,n1, \ldots, n by inserting nn into a quasi-increasing permutation of 1,…,n−11, \ldots, n-1
大提示:
nn 可以放在 n−1n-1 正前方、n−2n-2 正前方,或最后面;总是恰好 33 个位置,所以每加入新的 nn,数量乘以三
The nn can go immediately before n−1,n-1, immediately before n−2,n-2, or at the very end — always exactly 33 places, so the count triples with each new nn
解答:
设 SnS_n 为 1,…,n1, \ldots, n 的准递增排列个数。把 nn 插入一个 1,…,n−11, \ldots, n - 1 的准递增排列中:紧跟在 nn 后面的数必须至少为 n−2n - 2,所以 nn 可以放在 n−1n - 1 正前方、n−2n - 2 正前方,或最后面,恰好有 33 个位置;每种插入都会保持其他相邻条件不变。
反过来,从一个 1,…,n1, \ldots, n 的准递增排列中删除 nn 会留下一个 1,…,n−11, \ldots, n - 1 的准递增排列,因为当 n≥3n \ge 3 时,被删去的 nn 两侧的数满足 ak−1≤n−1≤ak+1+2a_{k-1} \le n - 1 \le a_{k+1} + 2。所以对 n≥3n \ge 3 有 Sn=3Sn−1S_n = 3S_{n-1}。
因为 S2=2S_2 = 2,所以 S7=2⋅35=486S_7 = 2 \cdot 3^5 = 486。
Let SnS_n be the number of quasi-increasing permutations of 1,…,n.1, \ldots, n. Insert nn into a quasi-increasing permutation of 1,…,n−1:1, \ldots, n - 1: the entry following nn must be at least n−2,n - 2, so nn can go immediately before n−1,n - 1, immediately before n−2,n - 2, or at the very end — exactly 33 positions, and each insertion keeps every other adjacent condition intact.
Conversely, deleting nn from a quasi-increasing permutation of 1,…,n1, \ldots, n leaves a quasi-increasing permutation of 1,…,n−1,1, \ldots, n - 1, since the entries around the deleted nn satisfy ak−1≤n−1≤ak+1+2a_{k-1} \le n - 1 \le a_{k+1} + 2 when n≥3.n \ge 3. So Sn=3Sn−1S_n = 3S_{n-1} for n≥3.n \ge 3.
Since S2=2,S_2 = 2, we get S7=2⋅35=486.S_7 = 2 \cdot 3^5 = 486.
第 9 题#9
完整试卷

其他年份的第 10 题