Difference between revisions of "2004 AIME I Problems/Problem 8"
(→Solution) |
I_like_pie (talk | contribs) |
||
Line 24: | Line 24: | ||
<math>((n-1)m \mod{n}, 0 \mod{n}).</math> | <math>((n-1)m \mod{n}, 0 \mod{n}).</math> | ||
− | If <math>\gcd(m,n) > 1</math>, then the star degenerates into a regular <math>\frac{n}{\gcd(m,n)}</math>-gon | + | If <math>\gcd(m,n) > 1</math>, then the star degenerates into a regular <math>\frac{n}{\gcd(m,n)}</math>-gon or a (2-vertex) line segment if |
<math>\frac{n}{\gcd(m,n)}= 2</math>. Therefore, we need to find all <math>m</math> such that <math>\gcd(m,n) = 1</math>. | <math>\frac{n}{\gcd(m,n)}= 2</math>. Therefore, we need to find all <math>m</math> such that <math>\gcd(m,n) = 1</math>. | ||
Note that <math>n = 1000 = 2^{3}5^{3}.</math> | Note that <math>n = 1000 = 2^{3}5^{3}.</math> | ||
− | Let <math>S = \{1,2,3,\ldots, 1000\}</math>, and <math>A_{i}= \{i \in S \mid i \textrm{ divides }1000\}</math>. The number of <math>m</math>'s that are not relatively prime to <math>1000</math> is: | + | Let <math>S = \{1,2,3,\ldots, 1000\}</math>, and <math>A_{i}= \{i \in S \mid i\, \textrm{ divides }\,1000\}</math>. The number of <math>m</math>'s that are not relatively prime to <math>1000</math> is: |
<math>\mid A_{2}\cup A_{5}\mid = \mid A_{2}\mid+\mid A_{5}\mid-\mid A_{2}\cap A_{5}\mid</math> | <math>\mid A_{2}\cup A_{5}\mid = \mid A_{2}\mid+\mid A_{5}\mid-\mid A_{2}\cap A_{5}\mid</math> | ||
<math>= \left\lfloor \frac{1000}{2}\right\rfloor+\left\lfloor \frac{1000}{5}\right\rfloor-\left\lfloor \frac{1000}{2 \cdot 5}\right\rfloor</math> | <math>= \left\lfloor \frac{1000}{2}\right\rfloor+\left\lfloor \frac{1000}{5}\right\rfloor-\left\lfloor \frac{1000}{2 \cdot 5}\right\rfloor</math> | ||
Line 43: | Line 43: | ||
== See also == | == See also == | ||
* [[2004 AIME I Problems]] | * [[2004 AIME I Problems]] | ||
− | |||
− | |||
− | |||
− | |||
− |
Revision as of 02:42, 6 November 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 half the count to get non-similar stars.
Number of non-similar 1000-pointed stars