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$ 处分段：分别计算每一段的路径数并相乘

Split the journey at the landmarks $13$ and $26:$ count routes for each segment and multiply

大提示：

有 $5$ 条路径连接相邻的 $13$ 的倍数，而有 $4$ 条路径跨过一段并跳过中间那个 $13$ 的倍数

There are $5$ routes between consecutive multiples of $13,$ and $4$ routes across a stretch that skips the multiple of $13$ in the middle

解答：

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

合并各段：经过两个标志点的路径数为 $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 题