2018 AIME II 第 15 题

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

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

15.

求满足以下条件的函数 ff 的个数:f 从 {0,1,2,3,4,5,6}\{0, 1, 2, 3, 4, 5, 6\} 映到整数, f(0)=0f(0) = 0f(6)=12f(6) = 12,并且对 {0,1,2,3,4,5,6}\{0, 1, 2, 3, 4, 5, 6\} 中所有 xxyy 都有 xyf(x)f(y)3xy \begin{aligned} |x - y| &\le |f(x) - f(y)| \\ &\le 3|x - y| \end{aligned}

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 xyf(x)f(y)3xy \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
解答:

di=f(i)f(i1)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(6k)k=184k3(6 - k) - k = 18 - 4k,所以 k1k \le 1。若没有差为负,则满足 a+b+c=6a + b + c = 6a+2b+3c=12a + 2b + 3c = 12 的解(其中 a,b,ca, b, c 分别计数 112233 的个数)为 (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}

d1<0d_1 \lt 0,则 f(2)2|f(2)| \ge 2f(2)d1+3f(2) \le d_1 + 3,迫使 d1=1d_1 = -1d2=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, 4dn+1<0d_{n+1} \lt 0, 则条件 f(n+1)f(n1)2|f(n+1) - f(n-1)| \ge 2f(n+2)f(n)2|f(n+2) - f(n)| \ge 2 迫使 dn+1=1d_{n+1} = -1dn=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(i1),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(6k)k=184k,3(6 - k) - k = 18 - 4k, so k1.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(n1)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 题