Question

Define una estrella regular de $n$ puntas como la unión de $n$ segmentos $\overline{P_1 P_2}, \overline{P_2 P_3}, \ldots, \overline{P_n P_1}$ tal que:

• los puntos $P_1, P_2, \ldots, P_n$ son coplanares y no hay tres de ellos colineales;

• cada uno de los $n$ segmentos corta al menos a otro de los segmentos en un punto que no es extremo;

• todos los ángulos en $P_1, P_2, \ldots, P_n$ son congruentes;

• todos los $n$ segmentos $\overline{P_1 P_2}, \overline{P_2 P_3}, \ldots, \overline{P_n P_1}$ son congruentes; y

• la trayectoria $P_1 P_2 \ldots P_n P_1$ gira en sentido antihorario con un ángulo menor que $180^\circ$ en cada vértice.

No existen estrellas regulares de $3$ puntas, $4$ puntas ni $6$ puntas. Todas las estrellas regulares de $5$ puntas son semejantes, pero hay dos estrellas regulares de $7$ puntas no semejantes. ¿Cuántas estrellas regulares de $1000$ puntas no semejantes hay?

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?

Respuesta

Solución:

Los ángulos congruentes y los segmentos congruentes obligan a que los vértices de una estrella regular estén igualmente espaciados en una circunferencia, recorridos dando un paso constante: numera $n$ puntos igualmente espaciados $0, 1, \ldots, n - 1$ y conecta cada $d$ -ésimo punto. La trayectoria visita los $n$ puntos exactamente cuando $\gcd(d, n) = 1,$ y los segmentos realmente se cruzan (formando una estrella y no un polígono convexo) exactamente cuando $2 \le d \le n - 2.$ Los pasos $d$ y $n - d$ trazan la misma figura en direcciones opuestas, mientras que valores distintos en otro caso dan estrellas no semejantes, ya que una homotecia que hiciera coincidir las circunferencias tendría que hacer coincidir los ángulos de giro.

Para $n = 1000 = 2^3 \cdot 5^3,$ la cantidad de $d$ con $\gcd(d, 1000) = 1$ es $1000\left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{5}\right) = 400.$ Al quitar $d = 1$ y $d = 999$ quedan $398$ valores, que se emparejan como $\{d, 1000 - d\},$ así que la cantidad de estrellas regulares de $1000$ puntas no semejantes es $\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 Problema 8

Solución:

El Problema 8 en otros años