Art of Problem Solving
Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

2004 AIME I Problems/Problem 8: Difference between revisions

← Older editNewer edit →
Casey001 (talk | contribs)
18 edits
I_like_pie (talk | contribs)
446 edits
No edit summary
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, a <math>\frac{n}{\gcd(m,n)}</math>-star, or a (2-vertex) line segment if
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]]
Euler <math>\phi</math> function gives the number of integers less than n that do not have a factor in common with n besides 1.
<math>\phi(n) = n(1-\frac{1}{p_1})(1-\frac{1}{p_2})(1-\frac{1}{p_3}) \cdots,</math>
where the <math>{p_i}</math>'s are distinct prime factors of n.
<math>\phi (1000) = 1000 \cdot (1-\frac{1}{2})(1-\frac{1}{5}) = 400.</math>

Revision as of 01:42, 6 November 2006

Problem

Define a regular $n$-pointed star to be the union of $n$ line segments $P_1P_2, P_2P_3,\ldots, P_nP_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 $P_2P_3,\ldots, P_nP_1$ are congruent, and
  • the path $P_1P_2, P_2P_3,\ldots, P_nP_1$ 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 $n$-star, we get a regular $n$-gon. We number the vertices of this $n$-gon in a counterclockwise direction: $0, 1, 2, 3, \ldots, n-1.$

A regular $n$-star will be formed if we choose a vertex number $m$, where $0 \le m \le n-1$, and then form the line segments by joining the following pairs of vertex numbers: $(0 \mod{n}, m \mod{n}),$ $(m \mod{n}, 2m \mod{n}),$ $(2m \mod{n}, 3m \mod{n}),$ $\cdots,$ $((n-2)m \mod{n}, (n-1)m \mod{n}),$ $((n-1)m \mod{n}, 0 \mod{n}).$

If $\gcd(m,n) > 1$, then the star degenerates into a regular $\frac{n}{\gcd(m,n)}$-gon or a (2-vertex) line segment if $\frac{n}{\gcd(m,n)}= 2$. Therefore, we need to find all $m$ such that $\gcd(m,n) = 1$.

Note that $n = 1000 = 2^{3}5^{3}.$

Let $S = \{1,2,3,\ldots, 1000\}$, and $A_{i}= \{i \in S \mid i\, \textrm{ divides }\,1000\}$. The number of $m$'s that are not relatively prime to $1000$ is: $\mid A_{2}\cup A_{5}\mid = \mid A_{2}\mid+\mid A_{5}\mid-\mid A_{2}\cap A_{5}\mid$ $= \left\lfloor \frac{1000}{2}\right\rfloor+\left\lfloor \frac{1000}{5}\right\rfloor-\left\lfloor \frac{1000}{2 \cdot 5}\right\rfloor$ $= 500+200-100 = 600.$

Vertex numbers $1$ and $n-1=999$ must be excluded as values for $m$ 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 $= \frac{1000-600-2}{2}= 199.$

See also

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2004_AIME_I_Problems/Problem_8&oldid=11204"