# Difference between revisions of "2004 AIME I Problems/Problem 8"

I_like_pie (talk | contribs) |
m (→Solution) |
||

Line 36: | Line 36: | ||

Vertex numbers <math>1</math> and <math>n-1=999</math> must be excluded as values for <math>m</math> since otherwise a regular n-gon, instead of an n-star, is formed. | Vertex numbers <math>1</math> and <math>n-1=999</math> must be excluded as values for <math>m</math> since otherwise a regular n-gon, instead of an n-star, is formed. | ||

− | The cases of a 1st line segment of (0, m) and (0, n-m) give the same star. Therefore we should | + | The cases of a 1st line segment of (0, m) and (0, n-m) give the same star. Therefore we should halve the count to get non-similar stars. |

Number of non-similar 1000-pointed stars | Number of non-similar 1000-pointed stars |

## Revision as of 17:35, 2 December 2006

## Problem

Define a regular -pointed star to be the union of line segments such that

- the points are coplanar and no three of them are collinear,
- each of the line segments intersects at least one of the other line segments at a point other than an endpoint,
- all of the angles at are congruent,
- all of the line segments are congruent, and
- the path turns counterclockwise at an angle of less than 180 degrees 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?

## Solution

Uses PIE (principle of inclusion-exclusion).

If we join the adjacent vertices of the regular -star, we get a regular -gon. We number the vertices of this -gon in a counterclockwise direction:

A regular -star will be formed if we choose a vertex number , where , and then form the line segments by joining the following pairs of vertex numbers:

If , then the star degenerates into a regular -gon or a (2-vertex) line segment if . Therefore, we need to find all such that .

Note that

Let , and . The number of 's that are not relatively prime to is:

Vertex numbers and must be excluded as values for since otherwise a regular n-gon, instead of an n-star, is formed.

The cases of a 1st line segment of (0, m) and (0, n-m) give the same star. Therefore we should halve the count to get non-similar stars.

Number of non-similar 1000-pointed stars