Question

一只青蛙被放在数轴原点，并按如下规则移动：每次移动时，青蛙前进到坐标更大的整数点中最近的 $3$ 的倍数，或前进到坐标更大的整数点中最近的 $13$ 的倍数。一个移动序列是由合法移动对应的坐标组成的序列，从 $0$ ，开始，以 $39$ 。结束。例如， $0, 3, 6, 13, 15, 26, 39$ 是一个移动序列。青蛙可能有多少个移动序列？

A frog is placed at the origin on the number line, and moves according to the following rule: in a given move, the frog advances to either the closest point with a greater integer coordinate that is a multiple of $3,$ or to the closest point with a greater integer coordinate that is a multiple of $13.$ A move sequence is a sequence of coordinates which correspond to valid moves, beginning with $0,$ and ending with $39.$ For example, $0, 3, 6, 13, 15, 26, 39$ is a move sequence. How many move sequences are possible for the frog?

答案

答案：169

知识点：乘法原理分类讨论

难度评级：2430

解答：

在标志点 $13$ 和 $26$ 处分段。从 $0$ 出发时，青蛙沿 $3$ 的倍数上升，并可从 $0, 3, 6, 9, 12$ 中任一点跳到 $13$ ，所以从 $0$ 到 $13$ 有 $5$ 条路径；同理，从 $13$ 到 $26$ 有 $5$ 条路径（从 $13, 15, 18, 21, 24$ 跳到 $26$ ），从 $26$ 到 $39$ 也有 $5$ 条路径。若完全跳过 $13$ ，青蛙必须在经过 $12 \to 15$ 时每次选择 $3$ 的倍数选项，然后从 $15, 18, 21, 24$ 中一点跳到 $26$ ；从 $0$ 到 $26$ 且避开 $13$ 有 $4$ 条路径。同理，从 $13$ 到 $39$ 且避开 $26$ 有 $4$ 条路径，从 $0$ 到 $39$ 且同时避开二者也有 $4$ 条路径。

合并各段：经过两个标志点的路径数为 $5 \cdot 5 \cdot 5 = 125$ ；只经过 $13$ 的为 $5 \cdot 4 = 20$ ；只经过 $26$ 的为 $4 \cdot 5 = 20$ ；两者都不经过的为 $4$ 。总数为 $125 + 20 + 20 + 4 = 169$ 。

Split the journey at the landmarks $13$ and $26.$ From $0$ the frog climbs the multiples of $3$ and may jump to $13$ from any of $0, 3, 6, 9, 12,$ giving $5$ routes from $0$ to $13;$ likewise there are $5$ routes from $13$ to $26$ (jump to $26$ from $13, 15, 18, 21, 24$ ) and $5$ from $26$ to $39.$ To skip $13$ entirely the frog must take the multiple-of- $3$ option every time through $12 \to 15,$ then jump to $26$ from one of $15, 18, 21, 24:$ $4$ routes from $0$ to $26$ avoiding $13.$ Similarly there are $4$ routes from $13$ to $39$ avoiding $26,$ and $4$ from $0$ to $39$ avoiding both.

Combining the segments: through both landmarks, $5 \cdot 5 \cdot 5 = 125;$ through $13$ only, $5 \cdot 4 = 20;$ through $26$ only, $4 \cdot 5 = 20;$ through neither, $4.$ The total is $125 + 20 + 20 + 4 = 169.$

2007 AIME I 第 6 题

答案：169

难度评级：2430

解答：

其他年份的第 6 题