AIME 2008 II · 第 10 题

Solution

We label our points using coordinates $0 \le x,y \le 3$, with the bottom-left point being $(0,0)$. By the Pythagorean Theorem, the distance between two points is $\sqrt{d_x^2 + d_y^2}$ where $0 \le d_x, d_y \le 3$; these yield the possible distances (in decreasing order)

$$\sqrt{18},\ \sqrt{13},\ \sqrt{10},\ \sqrt{9},\ \sqrt{8},\ \sqrt{5},\ \sqrt{4},\ \sqrt{2},\ \sqrt{1}$$ As these define $9$ lengths, so the maximum value of $m$ is $10$. For now, we assume that $m = 10$ is achievable. Because it is difficult to immediately impose restrictions on a path with increasing distances, we consider the paths in shrinking fashion. Note that the shrinking paths and growing paths are equivalent, but there are restrictions upon the locations of the first edges of the former.

The $\sqrt{18}$ length is only possible for one of the long diagonals, so our path must start with one of the $4$ corners of the grid. Without loss of generality (since the grid is rotationally symmetric), we let the vertex be $(0,0)$ and the endpoint be $(3,3)$.

The $\sqrt{13}$ length can now only go to $2$ points; due to reflectional symmetry about the main diagonal, we may WLOG let the next endpoint be $(1,0)$.

From $(1,0)$, there are two possible ways to move $\sqrt{10}$ away, either to $(0,3)$ or $(2,3)$. However, from $(0,3)$, there is no way to move $\sqrt{9}$ away, so we discard it as a possibility.

From $(2,3)$, the lengths of $\sqrt{8},\ \sqrt{5},\ \sqrt{4},\ \sqrt{2}$ fortunately are all determined, with the endpoint sequence being $(2,3)-(2,0)-(0,2)-(2,1)-(0,1)-(1,2)$.

From $(1,2)$, there are $3$ possible lengths of $\sqrt{1}$ (to either $(1,1),(2,2),(1,3)$). Thus, the number of paths is $r = 4 \cdot 2 \cdot 3 = 24$, and the answer is $mr = 10 \cdot 24 = \boxed{240}$.