Question

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?

Answer

Answer: 199

Concepts:Euler’s Totient Function regular polygon pairing and grouping

Difficulty rating: 2710

Solution:

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 Problem 8

Answer: 199

Difficulty rating: 2710

Solution:

Problem 8 in Other Years