2018 AIME II 第 8 题

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

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

8.

一只青蛙位于坐标平面的原点。从点 (x,y)(x, y) 出发,青蛙可以跳到 (x+1,y)(x + 1, y)(x+2,y)(x + 2, y)(x,y+1)(x, y + 1)(x,y+2)(x, y + 2) 中任一点。求青蛙从 (0,0)(0, 0) 出发并最终到达 (4,4)(4, 4) 的不同跳跃序列个数。

A frog is positioned at the origin in the coordinate plane. From the point (x,y),(x, y), the frog can jump to any of the points (x+1,y),(x + 1, y), (x+2,y),(x + 2, y), (x,y+1),(x, y + 1), or (x,y+2).(x, y + 2). Find the number of distinct sequences of jumps in which the frog begins at (0,0)(0, 0) and ends at (4,4).(4, 4).

答案:556
知识点:分拆与有序分拆多重集排列分类讨论
难度评级:2920
小提示:

向右的跳跃由若干 +1+1+2+2 组成且总和为 44,所以作为多重集合只能是 {1,1,1,1}\{1,1,1,1\}{1,1,2}\{1,1,2\},或 {2,2}\{2,2\},向上的跳跃同理

The rightward jumps are +1+1s and +2+2s summing to 4,4, so as a multiset they are {1,1,1,1},\{1,1,1,1\}, {1,1,2},\{1,1,2\}, or {2,2},\{2,2\}, and likewise for the upward jumps

大提示:

对每一对多重集合,所有跳跃的排列数是一个多项式系数;把九种情况相加

For each pair of multisets, the number of ways to order all the jumps is a multinomial coefficient; add up the nine cases

解答:

水平跳跃是若干长度为 1122 的步长,总和为 44,所以作为多重集合只能是 {1,1,1,1}\{1,1,1,1\}{1,1,2}\{1,1,2\},或 {2,2}\{2,2\},竖直跳跃也一样。对任意一对多重集合,所有跳跃的任意排列都是有效序列,排列数就是合并后多重集合的多项式系数。

九种情况给出 (84)=70,7!4!2!=105,6!4!2!=15 \begin{aligned} &\binom{8}{4} = 70, \\ &\quad \frac{7!}{4!\,2!} = 105, \\ &\quad \frac{6!}{4!\,2!} = 15 \end{aligned}\text{,}6!2!2!=180,5!2!2!=30,(42)=6 \begin{aligned} &\frac{6!}{2!\,2!} = 180, \\ &\quad \frac{5!}{2!\,2!} = 30, \\ &\quad \binom{4}{2} = 6 \end{aligned}\text{。}其中 10510515153030 各出现两次。

总数为 70+2105+21570 + 2 \cdot 105 + 2 \cdot 15 +180+230+6+ 180 + 2 \cdot 30 + 6 =556= 556

The horizontal jumps are steps of 11 or 22 summing to 4,4, so as a multiset they are {1,1,1,1},\{1,1,1,1\}, {1,1,2},\{1,1,2\}, or {2,2},\{2,2\}, and the same holds for the vertical jumps. For any choice of the two multisets, every ordering of all the jumps is a valid sequence, and the number of orderings is the multinomial coefficient of the combined multiset.

The nine cases give (84)=70,7!4!2!=105,6!4!2!=15, \begin{aligned} &\binom{8}{4} = 70, \\ &\quad \frac{7!}{4!\,2!} = 105, \\ &\quad \frac{6!}{4!\,2!} = 15, \end{aligned} 6!2!2!=180,5!2!2!=30,(42)=6. \begin{aligned} &\frac{6!}{2!\,2!} = 180, \\ &\quad \frac{5!}{2!\,2!} = 30, \\ &\quad \binom{4}{2} = 6. \end{aligned} The values 105,105, 15,15, and 3030 each occur twice.

The total is 70+2105+21570 + 2 \cdot 105 + 2 \cdot 15 +180+230+6+ 180 + 2 \cdot 30 + 6 =556.= 556.

第 7 题#7
完整试卷

其他年份的第 8 题