Difference between revisions of "2004 AIME I Problems/Problem 8"
(→See also) |
(→Problem) |
||
(9 intermediate revisions by 7 users not shown) | |||
Line 5: | Line 5: | ||
* each of the <math> n </math> line segments intersects at least one of the other line segments at a point other than an endpoint, | * each of the <math> n </math> line segments intersects at least one of the other line segments at a point other than an endpoint, | ||
* all of the angles at <math> P_1, P_2,\ldots, P_n </math> are congruent, | * all of the angles at <math> P_1, P_2,\ldots, P_n </math> are congruent, | ||
− | * all of the <math> n </math> line segments <math> P_2P_3,\ldots, P_nP_1 </math> are congruent, and | + | * all of the <math> n </math> line segments <math>P_1P_2, P_2P_3,\ldots, P_nP_1 </math> are congruent, and |
* the path <math> P_1P_2, P_2P_3,\ldots, P_nP_1 </math> turns counterclockwise at an angle of less than 180 degrees at each vertex. | * the path <math> P_1P_2, P_2P_3,\ldots, P_nP_1 </math> turns counterclockwise at an angle of less than 180 degrees at each vertex. | ||
Line 11: | Line 11: | ||
== Solution == | == Solution == | ||
− | + | We use the [[Principle of Inclusion-Exclusion]] (PIE). | |
− | If we join the adjacent vertices of the regular <math>n</math>-star, we get a regular <math>n</math>-gon. We number the vertices of this <math>n</math>-gon in a counterclockwise direction: | + | If we join the adjacent vertices of the regular <math>n</math>-star, we get a regular <math>n</math>-gon. We number the vertices of this <math>n</math>-gon in a counterclockwise direction: <math>0, 1, 2, 3, \ldots, n-1.</math> |
− | <math>0, 1, 2, 3, \ldots, n-1.</math> | ||
A regular <math>n</math>-star will be formed if we choose a vertex number <math>m</math>, where <math>0 \le m \le n-1</math>, and then form the line segments by joining the following pairs of vertex numbers: | A regular <math>n</math>-star will be formed if we choose a vertex number <math>m</math>, where <math>0 \le m \le n-1</math>, and then form the line segments by joining the following pairs of vertex numbers: | ||
Line 29: | Line 28: | ||
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 36: | Line 35: | ||
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. |
− | + | Therefore, the number of non-similar 1000-pointed stars is <math>\frac{1000-600-2}{2}= \boxed{199}.</math> | |
− | <math> | + | |
+ | ---- | ||
+ | |||
+ | Note that in general, the number of <math>n</math>-pointed stars is given by <math>\frac{\phi(n)}{2} - 1</math> (dividing by <math>2</math> to remove the reflectional symmetry, subtracting <math>1</math> to get rid of the <math>1</math>-step case), where <math>\phi(n)</math> is the [[Euler's totient function]]. It is well-known that <math>\phi(n) = n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\cdots \left(1-\frac{1}{p_n}\right)</math>, where <math>p_1,\,p_2,\ldots,\,p_n</math> are the distinct prime factors of <math>n</math>. Thus <math>\phi(1000) = 1000\left(1 - \frac 12\right)\left(1 - \frac 15\right) = 400</math>, and the answer is <math>\frac{400}{2} - 1 = 199</math>. | ||
== See also == | == See also == | ||
− | + | {{AIME box|year=2004|n=I|num-b=7|num-a=9}} | |
− | |||
− | |||
− | |||
− | + | [[Category:Intermediate Combinatorics Problems]] | |
+ | [[Category:Intermediate Number Theory Problems]] | ||
+ | {{MAA Notice}} |
Latest revision as of 21:26, 5 June 2021
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
We use the Principle of Inclusion-Exclusion (PIE).
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.
Therefore, the number of non-similar 1000-pointed stars is
Note that in general, the number of -pointed stars is given by
(dividing by
to remove the reflectional symmetry, subtracting
to get rid of the
-step case), where
is the Euler's totient function. It is well-known that
, where
are the distinct prime factors of
. Thus
, and the answer is
.
See also
2004 AIME I (Problems • Answer Key • Resources) | ||
Preceded by Problem 7 |
Followed by Problem 9 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.