2018 AIME II 第 15 题

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

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

15.

求从 {0,1,2,3,4,5,6}\{0, 1, 2, 3, 4, 5, 6\} 映到整数集的函数 ff 的个数,使得 f(0)=0f(0) = 0、f(6)=12f(6) = 12,并且∣x−y∣≤∣f(x)−f(y)∣≤3∣x−y∣ \begin{aligned} |x - y| &\le |f(x) - f(y)| \\ &\le 3|x - y| \end{aligned} 对 {0,1,2,3,4,5,6}\{0, 1, 2, 3, 4, 5, 6\} 中所有 xx 与 yy 都成立。

Find the number of functions ff from {0,1,2,3,4,5,6}\{0, 1, 2, 3, 4, 5, 6\} to the integers such that f(0)=0,f(0) = 0, f(6)=12,f(6) = 12, and ∣x−y∣≤∣f(x)−f(y)∣≤3∣x−y∣ \begin{aligned} |x - y| &\le |f(x) - f(y)| \\ &\le 3|x - y| \end{aligned} for all xx and yy in {0,1,2,3,4,5,6}.\{0, 1, 2, 3, 4, 5, 6\}.

答案:185
知识点:分拆与有序分拆多重集排列分类讨论极限情形界定
难度评级:3370
小提示:

相邻函数值之差的绝对值为 11、22,或 33,且六个差的总和为 1212;证明至多有一个差为负

Consecutive values differ by 1,1, 2,2, or 33 in absolute value and the six differences sum to 12;12; show at most one difference can be negative

大提示:

分三种情况处理:没有下降;下降发生在端点;下降发生在内部,此时它被迫是 −1-1,且两侧都是 +3+3

Handle three cases: no decrease; a decrease at either end; an interior decrease, which is forced to be −1-1 flanked by two +3+3s

解答:

设 di=f(i)−f(i−1)d_i = f(i) - f(i-1),所以每个 ∣di∣∈{1,2,3}|d_i| \in \{1, 2, 3\},且 d1+⋯+d6=12d_1 + \cdots + d_6 = 12。若有 kk 个差为负,则总和最多为 3(6−k)−k=18−4k3(6 - k) - k = 18 - 4k,所以 k≤1k \le 1。若没有差为负,则满足 a+b+c=6a + b + c = 6、a+2b+3c=12a + 2b + 3c = 12 的解(其中 a,b,ca, b, c 分别计数 11、22、33 的个数)为 (0,6,0)(0,6,0)、(1,4,1)(1,4,1)、(2,2,2)(2,2,2)、(3,0,3)(3,0,3)。所有这些排列都满足任意两点条件,给出 (60,6,0)+(61,4,1)+(62,2,2)+(63,0,3)=1+30+90+20=141。 \begin{aligned} &\binom{6}{0,6,0} + \binom{6}{1,4,1} \\ &\quad {}+ \binom{6}{2,2,2} + \binom{6}{3,0,3} \\ &= 1 + 30 + 90 + 20 = 141 \end{aligned}\text{。}

若 d1<0d_1 \lt 0,则 ∣f(2)∣≥2|f(2)| \ge 2 且 f(2)≤d1+3f(2) \le d_1 + 3,迫使 d1=−1d_1 = -1 且 d2=3d_2 = 3;剩余四个差为正且和为 1010,给出 (41,0,3)+(40,2,2)=4+6=10\binom{4}{1,0,3} + \binom{4}{0,2,2} = 4 + 6 = 10 个函数,而 d6<0d_6 \lt 0 的情况对称:两端合计 2020 个。最后,若对某个 n=1,2,3,4n = 1, 2, 3, 4 有 dn+1<0d_{n+1} \lt 0,则条件 ∣f(n+1)−f(n−1)∣≥2|f(n+1) - f(n-1)| \ge 2 与 ∣f(n+2)−f(n)∣≥2|f(n+2) - f(n)| \ge 2 迫使 dn+1=−1d_{n+1} = -1 且 dn=dn+2=3d_n = d_{n+2} = 3。另外三个差为正且和为 77,可以是两个 33 和一个 11,或一个 33 和两个 22,每种各有 33 种顺序:所以这 44 个位置中每个都有 66 种方式,共 2424 个函数。

总数为 141+20+24=185141 + 20 + 24 = 185。

Let di=f(i)−f(i−1),d_i = f(i) - f(i-1), so each ∣di∣∈{1,2,3}|d_i| \in \{1, 2, 3\} and d1+⋯+d6=12.d_1 + \cdots + d_6 = 12. If kk of the differences were negative, the sum would be at most 3(6−k)−k=18−4k,3(6 - k) - k = 18 - 4k, so k≤1.k \le 1. If no difference is negative, the solutions of a+b+c=6,a + b + c = 6, a+2b+3c=12a + 2b + 3c = 12 (with a,b,ca, b, c counting 11s, 22s, 33s) are (0,6,0),(0,6,0), (1,4,1),(1,4,1), (2,2,2),(2,2,2), (3,0,3),(3,0,3), and all such orderings satisfy every pair condition, giving (60,6,0)+(61,4,1)+(62,2,2)+(63,0,3)=1+30+90+20=141. \begin{aligned} &\binom{6}{0,6,0} + \binom{6}{1,4,1} \\ &\quad {}+ \binom{6}{2,2,2} + \binom{6}{3,0,3} \\ &= 1 + 30 + 90 + 20 = 141. \end{aligned}

If d1<0,d_1 \lt 0, then ∣f(2)∣≥2|f(2)| \ge 2 with f(2)≤d1+3f(2) \le d_1 + 3 forces d1=−1d_1 = -1 and d2=3;d_2 = 3; the remaining four differences are positive and sum to 10,10, giving (41,0,3)+(40,2,2)=4+6=10\binom{4}{1,0,3} + \binom{4}{0,2,2} = 4 + 6 = 10 functions, and the case d6<0d_6 \lt 0 is symmetric: 2020 in all. Finally, if dn+1<0d_{n+1} \lt 0 for some n=1,2,3,4,n = 1, 2, 3, 4, the pair conditions ∣f(n+1)−f(n−1)∣≥2|f(n+1) - f(n-1)| \ge 2 and ∣f(n+2)−f(n)∣≥2|f(n+2) - f(n)| \ge 2 force dn+1=−1d_{n+1} = -1 and dn=dn+2=3.d_n = d_{n+2} = 3. The other three differences are positive and sum to 7,7, achievable as two 33s and a 11 or a 33 and two 22s, each in 33 orders: 66 ways for each of the 44 positions, or 2424 functions.

The total is 141+20+24=185.141 + 20 + 24 = 185.

第 14 题#14
完整试卷

其他年份的第 15 题