Question

定义一个正 $n$ 角星为 $n$ 条线段 $\overline{P_1 P_2}$ 、 $\overline{P_2 P_3}$ 、 $\ldots$ 、 $\overline{P_n P_1}$ 的并集，并满足：

• 点 $P_1$ 、 $P_2$ 、 $\ldots$ 、 $P_n$ 共面，且任意三点不共线；

• 每一条这 $n$ 条线段都至少与另一条线段在非端点处相交；

• 在 $P_1$ 、 $P_2$ 、 $\ldots$ 、 $P_n$ 处的所有角都全等；

• 这 $n$ 条线段 $\overline{P_1 P_2}$ 、 $\overline{P_2 P_3}$ 、 $\ldots$ 、 $\overline{P_n P_1}$ 都全等；并且

• 路径 $P_1 P_2 \ldots P_n P_1$ 在每个顶点都以小于 $180^\circ$ 的角逆时针转向。

不存在正 $3$ 角星、正 $4$ 角星或正 $6$ 角星。所有正 $5$ 角星都相似，但有两个不相似的正 $7$ 角星。有多少个不相似的正 $1000$ 角星？

Define a regular $n$ -pointed star to be the union of $n$ line segments $\overline{P_1 P_2},$ $\overline{P_2 P_3},$ $\ldots,$ $\overline{P_n P_1}$ such that

• the points $P_1,$ $P_2,$ $\ldots,$ $P_n$ are coplanar and no three of them are collinear,

• each of the $n$ line segments intersects at least one of the other line segments at a point other than an endpoint,

• all of the angles at $P_1,$ $P_2,$ $\ldots,$ $P_n$ are congruent,

• all of the $n$ line segments $\overline{P_1 P_2},$ $\overline{P_2 P_3},$ $\ldots,$ $\overline{P_n P_1}$ are congruent, and

• the path $P_1 P_2 \ldots P_n P_1$ turns counterclockwise at an angle of less than $180^\circ$ at each vertex.

There are no regular $3$ -pointed, $4$ -pointed, or $6$ -pointed stars. All regular $5$ -pointed stars are similar, but there are two non-similar regular $7$ -pointed stars. How many non-similar regular $1000$ -pointed stars are there?

答案

答案：199

知识点：欧拉函数正多边形配对与分组

难度评级：2710

小提示：

正 $n$ 角星每隔 $d$ 个点连接一次，这些点是圆上的 $n$ 个等距点；其中 $d$ 与 $n$ 互质

A regular $n$ -pointed star joins every $d$ th of $n$ equally spaced points on a circle, where $d$ is relatively prime to $n$

大提示：

排除 $d = 1$ 和 $d = n - 1$ ，它们给出凸多边形，并注意 $d$ 与 $n - d$ 描出相似的星形

Exclude $d = 1$ and $d = n - 1,$ which give a convex polygon, and note that $d$ and $n - d$ trace similar stars

解答：

全等的角和全等的线段迫使正星形的顶点等距地位于同一个圆上，并且按固定步长访问：将 $n$ 个等距点编号为 $0, 1, \ldots, n - 1$ ，每隔 $d$ 个点连接一次。路径恰好访问全部 $n$ 个点的条件是 $\gcd(d, n) = 1$ ；而真正发生交叉（形成星形而非凸多边形）恰好在 $2 \le d \le n - 2$ 时。步长 $d$ 和 $n - d$ 以相反方向描出同一图形，而除此之外不同的步长给出不相似的星形，因为若用伸缩变换匹配圆，就还必须匹配转角。

对于 $n = 1000 = 2^3 \cdot 5^3$ ，这样的 $d$ 满足 $\gcd(d, 1000) = 1$ ，共有 $1000\left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{5}\right) = 400$ 个。去掉 $d = 1$ 和 $d = 999$ 后剩下 $398$ 个值，它们按 $\{d, 1000 - d\}$ 成对，所以不相似的正 $1000$ 角星个数是 $\frac{398}{2} = 199$ 。

The congruent angles and congruent segments force the vertices of a regular star to be equally spaced on a circle, visited by taking a constant step: number $n$ equally spaced points $0, 1, \ldots, n - 1$ and connect every $d$ th point. The path visits all $n$ points exactly when $\gcd(d, n) = 1,$ and the segments actually cross (making a star rather than a convex polygon) exactly when $2 \le d \le n - 2.$ Steps $d$ and $n - d$ trace the same figure in opposite directions, while different values otherwise give non-similar stars, since a dilation matching the circles would have to match the turning angles.

For $n = 1000 = 2^3 \cdot 5^3,$ the number of $d$ with $\gcd(d, 1000) = 1$ is $1000\left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{5}\right) = 400.$ Removing $d = 1$ and $d = 999$ leaves $398$ values, which pair up as $\{d, 1000 - d\},$ so the number of non-similar regular $1000$ -pointed stars is $\frac{398}{2} = 199.$

2004 AIME I 第 8 题

答案：199

难度评级：2710

小提示：

大提示：

解答：

其他年份的第 8 题