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

Difference between revisions of "2009 AIME II Problems/Problem 13"

(New page: '''Problem''' Let <math>A</math> and <math>B</math> be the endpoints of a semicircular arc of radius <math>2</math>. The arc is divided into seven congruent arcs by six equally spaced poi...)
 
(f)
 
(30 intermediate revisions by 13 users not shown)
Line 1: Line 1:
−
'''Problem'''
+
== Problem ==
 +
 
  
 
Let <math>A</math> and <math>B</math> be the endpoints of a semicircular arc of radius <math>2</math>. The arc is divided into seven congruent arcs by six equally spaced points <math>C_1</math>, <math>C_2</math>, <math>\dots</math>, <math>C_6</math>. All chords of the form <math>\overline {AC_i}</math> or <math>\overline {BC_i}</math> are drawn. Let <math>n</math> be the product of the lengths of these twelve chords. Find the remainder when <math>n</math> is divided by <math>1000</math>.  
 
Let <math>A</math> and <math>B</math> be the endpoints of a semicircular arc of radius <math>2</math>. The arc is divided into seven congruent arcs by six equally spaced points <math>C_1</math>, <math>C_2</math>, <math>\dots</math>, <math>C_6</math>. All chords of the form <math>\overline {AC_i}</math> or <math>\overline {BC_i}</math> are drawn. Let <math>n</math> be the product of the lengths of these twelve chords. Find the remainder when <math>n</math> is divided by <math>1000</math>.  
  
−
'''Solution'''
+
 
 +
== Solution ==
 +
 
 +
=== Solution 1 ===
 +
 
 +
Let the radius be 1 instead. All lengths will be halved so we will multiply by <math>2^{12}</math> at the end. Place the semicircle on the complex plane, with the center of the circle being 0 and the diameter being the real axis. Then <math>C_1,\ldots, C_6</math> are 6 of the 14th roots of unity. Let <math>\omega=\text{cis}\frac{360^{\circ}}{14}</math>; then <math>C_1,\ldots, C_6</math> correspond to <math>\omega,\ldots, \omega^6</math>. Let <math>C_1',\ldots, C_6'</math> be their reflections across the diameter. These points correspond to <math>\omega^8\ldots, \omega^{13}</math>. Then the lengths of the segments are <math>|1-\omega|,\ldots, |1-\omega^6|,|1-\omega^8|,\ldots |1-\omega^{13}|</math>. Noting that <math>B</math> represents 1 in the complex plane, the desired product is
 +
<cmath>
 +
\begin{align*}
 +
BC_1\cdots BC_6 \cdot AC_1\cdots AC_6&=
 +
BC_1\cdots BC_6 \cdot BC_1'\cdots BC_6'\\
 +
&=
 +
|(x-\omega^1)\ldots(x-\omega^6)(x-\omega^8)\ldots(x-\omega^{13})|
 +
\end{align*}</cmath>
 +
 
 +
for <math>x=1</math>.
 +
However, the polynomial <math>(x-\omega^1)\ldots(x-\omega^6)(x-\omega^8)\ldots(x-\omega^{13})</math> has as its zeros all 14th roots of unity except for <math>-1</math> and <math>1</math>. Hence
 +
<cmath>
 +
(x-\omega^1)\ldots(x-\omega^6)(x-\omega^8)\ldots(x-\omega^{13})=\frac{x^{14}-1}{(x-1)(x+1)}=x^{12}+x^{10}+\cdots +x^2+1.
 +
</cmath>
 +
Thus the product is <math>|x^{12}+\cdots +x^2+1|=7</math> when the radius is 1, and the product is <math>2^{12}\cdot 7=28672</math>. Thus the answer is <math>\boxed {672}</math>.
 +
 
 +
=== Solution 2 ===
  
 
Let <math>O</math> be the midpoint of <math>A</math> and <math>B</math>. Assume <math>C_1</math> is closer to <math>A</math> instead of <math>B</math>.  <math>\angle AOC_1</math> = <math>\frac {\pi}{7}</math>. Using the [[Law of Cosines]],  
 
Let <math>O</math> be the midpoint of <math>A</math> and <math>B</math>. Assume <math>C_1</math> is closer to <math>A</math> instead of <math>B</math>.  <math>\angle AOC_1</math> = <math>\frac {\pi}{7}</math>. Using the [[Law of Cosines]],  
  
−
<math>\overline {AC_1}</math> = <math>8 - 8 cos \frac {\pi}{7}</math>
+
<math>\overline {AC_1}^2</math> = <math>8 - 8 \cos \frac {\pi}{7}</math>, 
−
<math>\overline {AC_2}</math> = <math>8 - 8 cos \frac {2\pi}{7}</math>
+
<math>\overline {AC_2}^2</math> = <math>8 - 8 \cos \frac {2\pi}{7}</math>,
 
.
 
.
 
.
 
.
 
.
 
.
−
<math>\overline {AC_6}</math> = <math>8 - 8 cos \frac {6\pi}{7}</math>
+
<math>\overline {AC_6}^2</math> = <math>8 - 8 \cos \frac {6\pi}{7}</math>                               
 +
 
 +
So <math>n</math> = <math>(8^6)(1 - \cos \frac {\pi}{7})(1 - \cos \frac {2\pi}{7})\dots(1 - \cos \frac{6\pi}{7})</math>. It can be rearranged to form
 +
 
 +
<math>n</math> = <math>(8^6)(1 - \cos \frac {\pi}{7})(1 - \cos \frac {6\pi}{7})\dots(1 - \cos \frac {3\pi}{7})(1 - \cos \frac {4\pi}{7})</math>.
 +
 
 +
Since <math>\cos a = - \cos (\pi - a)</math>, we have
 +
 
 +
<math>n</math> = <math>(8^6)(1 - \cos \frac {\pi}{7})(1 + \cos \frac {\pi}{7}) \dots (1 - \cos \frac {3\pi}{7})(1 + \cos \frac {3\pi}{7})</math>
 +
 
 +
= <math>(8^6)(1 - \cos^2 \frac {\pi}{7})(1 - \cos^2 \frac {2\pi}{7})(1 - \cos^2 \frac {3\pi}{7})</math>
 +
 
 +
= <math>(8^6)(\sin^2 \frac {\pi}{7})(\sin^2 \frac {2\pi}{7})(\sin^2 \frac {3\pi}{7})</math>
 +
 
 +
It can be shown that <math>\sin \frac {\pi}{7} \sin \frac {2\pi}{7} \sin \frac {3\pi}{7}</math> = <math>\frac {\sqrt {7}}{8}</math>, so <math>n</math> = <math>8^6(\frac {\sqrt {7}}{8})^2</math> = <math>7(8^4)</math> = <math>28672</math>, so the answer is <math>\boxed {672}</math>
 +
 
 +
=== Solution 3 ===
 +
 
 +
Note that for each <math>k</math> the triangle <math>ABC_k</math> is a right triangle. Hence the product <math>AC_k \cdot BC_k</math> is twice the area of the triangle <math>ABC_k</math>. Knowing that <math>AB=4</math>, the area of <math>ABC_k</math> can also be expressed as <math>2c_k</math>, where <math>c_k</math> is the length of the altitude from <math>C_k</math> onto <math>AB</math>. Hence we have <math>AC_k \cdot BC_k = 4c_k</math>.
 +
 
 +
By the definition of <math>C_k</math> we obviously have <math>c_k = 2\sin\frac{k\pi}7</math>.
 +
 
 +
From these two observations we get that the product we should compute is equal to <math> 8^6 \cdot \prod_{k=1}^6 \sin \frac{k\pi}7 </math>, which is the same identity as in Solution 2.
 +
 
 +
=== Computing the product of sines ===
 +
 
 +
In this section we show one way how to evaluate the product <math>\prod_{k=1}^6 \sin \frac{k\pi}7 = \prod_{k=1}^3 (\sin \frac{k\pi}7)^2 </math>.
 +
 
 +
Let <math>\omega_k = \cos \frac{2k\pi}7 + i\sin \frac{2k\pi}7</math>. The numbers <math>1,\omega_1,\omega_2,\dots,\omega_6</math> are the <math>7</math>-th complex roots of unity. In other words, these are the roots of the polynomial <math>x^7-1</math>. Then the numbers <math>\omega_1,\omega_2,\dots,\omega_6</math> are the roots of the polynomial <math>\frac{x^7-1}{x-1} = x^6+x^5+\cdots+x+1</math>.
 +
 
 +
We just proved the identity <math>\prod_{k=1}^6 (x - \omega_k) = x^6+x^5+\cdots+x+1</math>.
 +
Substitute <math>x=1</math>. The right hand side is obviously equal to <math>7</math>. Let's now examine the left hand side.
 +
We have:
 +
 
 +
<cmath>
 +
\begin{align*}
 +
(1-\omega_k)(1-\omega_{7-k})=|1-\omega_k|^2
 +
& = \left( 1-\cos \frac{2k\pi}7 \right)^2 + \left( \sin \frac{2k\pi}7 \right)^2
 +
\\
 +
& = 2-2\cos \frac{2k\pi}7
 +
\\
 +
& = 2-2 \left( 1 - 2 \left( \sin \frac{k\pi}7 \right)^2 \right)
 +
\\
 +
& = 4\left( \sin \frac{k\pi}7 \right)^2
 +
\end{align*}
 +
</cmath>
 +
 
 +
Therefore the size of the left hand side in our equation is <math>\prod_{k=1}^3 4 (\sin \frac{k\pi}7)^2 = 2^6 \prod_{k=1}^3 (\sin \frac{k\pi}7)^2</math>. As the right hand side is <math>7</math>, we get that <math>\prod_{k=1}^3 (\sin \frac{k\pi}7)^2 = \frac{7}{2^6}</math>.
 +
 
 +
===Solution 4 (Product of Sines)===
 +
 
 +
<i><b>Lemma 1:</b> A chord <math>ab</math> of a circle with center <math>O</math> and radius <math>r</math> has length <math>2r\sin\left(\dfrac{\angle AOB}{2}\right)</math>.</i>
 +
 
 +
<i><b>Proof:</b> Denote <math>H</math> as the projection from <math>O</math> to line <math>AB</math>. Then, by definition, <math>HA=HB=r\sin\left(\dfrac{\angle AOB}{2}\right)</math>. Thus, <math>AB = 2r\sin\left(\dfrac{\angle AOB}{2}\right)</math>, which concludes the proof.</i>
 +
 
 +
<i><b>Lemma 2:</b> <math>\prod_{k=1}^{n-1} \sin \dfrac{k\pi}{n} = \dfrac{n}{2^{n-1}}</math></i>
 +
 
 +
<i><b>Proof:</b> Let <math>w=\text{cis}\;\dfrac{\pi}{n}</math>. Thus,
 +
<cmath>\prod_{k=1}^{n-1} \sin \dfrac{k\pi}{n} = \prod_{k=1}^{n-1} \dfrac{w^k-w^{-k}}{2i} = \dfrac{w^{\frac{n(n-1)}{2}}}{(2i)^{n-1}}\prod_{k=1}^{n-1} (1-w^{-2k}) = \dfrac{1}{2^{n-1}}\prod_{k=1}^{n-1} (1-w^{-2k})</cmath>
 +
Since, <math>w^{-2k}</math> are just the <math>n</math>th roots of unity excluding <math>1</math>, by Vieta's, <math>\prod_{k=1}^{n-1} \sin \dfrac{k\pi}{n}=\dfrac{1}{2^{n-1}}\prod_{k=1}^{n-1} (1-w^{-2k}) = \dfrac{n}{2^{n-1}}</math>, thus completing the proof.
 +
</i>
 +
 
 +
By Lemma 1, the length <math>AC_k=2r\sin\dfrac{k\pi}{14}</math> and similar lengths apply for <math>BC_k</math>. Now, the problem asks for <math>\left(\prod_{k=1}^6 \left(4\sin\dfrac{k\pi}{14}\right)\right)^2</math>. This can be rewritten, due to <math>\sin \theta = \sin (\pi-\theta)</math>, as <math>\prod_{k=1}^6 \left(4\sin\dfrac{k\pi}{14}\right) \cdot \prod_{k=8}^{13} \left(4\sin\dfrac{k\pi}{14}\right) = \dfrac{1}{\sin \dfrac{7\pi}{14}}\cdot \prod_{k=1}^{13} \left(4\sin\dfrac{k\pi}{14}\right) = \prod_{k=1}^{13} \left(4\sin\dfrac{k\pi}{14}\right).</math> By Lemma 2, this furtherly boils down to <math>4^{12}\cdot \dfrac{14}{2^{13}} = 7\cdot 2^{12} = \boxed{672} \; \text{(mod }1000\text{)}</math>
 +
 
 +
<b>~Solution by  sml1809</b>
 +
 
  
−
So <math>n</math> = <math>(8^6)(1 - cos \frac {\pi}{7})(1 - cos \frac {2\pi}{7})\dots(1 - cos \frac{6\pi}{7})</math>. It can be rearranged to form
+
== Video Solution ==
  
−
<math>n</math> = <math>(8^6)(1 - cos \frac {\pi}{7})(1 - cos \frac {6\pi}{7})\dots(1 - cos \frac {3\pi}{7})(1 - cos \frac {2\pi}{4})</math>.  
+
https://youtu.be/TrKxzgR7V8U?si=FFOBCJxjGrg9sWGC
  
−
<math>cos a</math> = - <math>cos (\pi - a)</math>, so we have
+
~MathProblemSolvingSkills.com
  
−
<math>n</math> = <math>(8^6)(1 - cos \frac {\pi}{7})(1 + cos \frac {\pi}{7}) </math>\dots<math> (1 - cos \frac {3\pi}{7})(1 + cos \frac {3\pi}{7})</math>
 
  
−
= <math>(8^6)(1 - cos^2 \frac {\pi}{7})(1 - cos^2 \frac {2\pi}{7})(1 - cos^2 \frac {3\pi}{7})</math>
 
  
−
= <math>(8^6)(sin^2 \frac {\pi}{7})(sin^2 \frac {2\pi}{7})(sin^2 \frac {3\pi}{7})</math>
+
== See Also ==
  
−
It can be shown that sin <math>\frac {\pi}{7}</math> sin <math>\frac {2\pi}{7}</math> sin <math>\frac {3\pi}{7}</math> = <math>\frac {\sqrt {7}}{8}</math>, so <math>n</math> = <math>8^6(\frac {\sqrt {7}}{8})^2</math> = <math>7(8^4)</math> = <math>28672</math>, so the answer is <math>\boxed {672}</math>
+
{{AIME box|year=2009|n=II|num-b=12|num-a=14}}
 +
{{MAA Notice}}

Latest revision as of 21:32, 3 October 2024

Problem

Let $A$ and $B$ be the endpoints of a semicircular arc of radius $2$. The arc is divided into seven congruent arcs by six equally spaced points $C_1$, $C_2$, $\dots$, $C_6$. All chords of the form $\overline {AC_i}$ or $\overline {BC_i}$ are drawn. Let $n$ be the product of the lengths of these twelve chords. Find the remainder when $n$ is divided by $1000$.


Solution

Solution 1

Let the radius be 1 instead. All lengths will be halved so we will multiply by $2^{12}$ at the end. Place the semicircle on the complex plane, with the center of the circle being 0 and the diameter being the real axis. Then $C_1,\ldots, C_6$ are 6 of the 14th roots of unity. Let $\omega=\text{cis}\frac{360^{\circ}}{14}$; then $C_1,\ldots, C_6$ correspond to $\omega,\ldots, \omega^6$. Let $C_1',\ldots, C_6'$ be their reflections across the diameter. These points correspond to $\omega^8\ldots, \omega^{13}$. Then the lengths of the segments are $|1-\omega|,\ldots, |1-\omega^6|,|1-\omega^8|,\ldots |1-\omega^{13}|$. Noting that $B$ represents 1 in the complex plane, the desired product is \begin{align*} BC_1\cdots BC_6 \cdot AC_1\cdots AC_6&= BC_1\cdots BC_6 \cdot BC_1'\cdots BC_6'\\ &= |(x-\omega^1)\ldots(x-\omega^6)(x-\omega^8)\ldots(x-\omega^{13})| \end{align*}

for $x=1$. However, the polynomial $(x-\omega^1)\ldots(x-\omega^6)(x-\omega^8)\ldots(x-\omega^{13})$ has as its zeros all 14th roots of unity except for $-1$ and $1$. Hence \[(x-\omega^1)\ldots(x-\omega^6)(x-\omega^8)\ldots(x-\omega^{13})=\frac{x^{14}-1}{(x-1)(x+1)}=x^{12}+x^{10}+\cdots +x^2+1.\] Thus the product is $|x^{12}+\cdots +x^2+1|=7$ when the radius is 1, and the product is $2^{12}\cdot 7=28672$. Thus the answer is $\boxed {672}$.

Solution 2

Let $O$ be the midpoint of $A$ and $B$. Assume $C_1$ is closer to $A$ instead of $B$. $\angle AOC_1$ = $\frac {\pi}{7}$. Using the Law of Cosines,

$\overline {AC_1}^2$ = $8 - 8 \cos \frac {\pi}{7}$, $\overline {AC_2}^2$ = $8 - 8 \cos \frac {2\pi}{7}$, . . . $\overline {AC_6}^2$ = $8 - 8 \cos \frac {6\pi}{7}$

So $n$ = $(8^6)(1 - \cos \frac {\pi}{7})(1 - \cos \frac {2\pi}{7})\dots(1 - \cos \frac{6\pi}{7})$. It can be rearranged to form

$n$ = $(8^6)(1 - \cos \frac {\pi}{7})(1 - \cos \frac {6\pi}{7})\dots(1 - \cos \frac {3\pi}{7})(1 - \cos \frac {4\pi}{7})$.

Since $\cos a = - \cos (\pi - a)$, we have

$n$ = $(8^6)(1 - \cos \frac {\pi}{7})(1 + \cos \frac {\pi}{7}) \dots (1 - \cos \frac {3\pi}{7})(1 + \cos \frac {3\pi}{7})$

= $(8^6)(1 - \cos^2 \frac {\pi}{7})(1 - \cos^2 \frac {2\pi}{7})(1 - \cos^2 \frac {3\pi}{7})$

= $(8^6)(\sin^2 \frac {\pi}{7})(\sin^2 \frac {2\pi}{7})(\sin^2 \frac {3\pi}{7})$

It can be shown that $\sin \frac {\pi}{7} \sin \frac {2\pi}{7} \sin \frac {3\pi}{7}$ = $\frac {\sqrt {7}}{8}$, so $n$ = $8^6(\frac {\sqrt {7}}{8})^2$ = $7(8^4)$ = $28672$, so the answer is $\boxed {672}$

Solution 3

Note that for each $k$ the triangle $ABC_k$ is a right triangle. Hence the product $AC_k \cdot BC_k$ is twice the area of the triangle $ABC_k$. Knowing that $AB=4$, the area of $ABC_k$ can also be expressed as $2c_k$, where $c_k$ is the length of the altitude from $C_k$ onto $AB$. Hence we have $AC_k \cdot BC_k = 4c_k$.

By the definition of $C_k$ we obviously have $c_k = 2\sin\frac{k\pi}7$.

From these two observations we get that the product we should compute is equal to $8^6 \cdot \prod_{k=1}^6 \sin \frac{k\pi}7$, which is the same identity as in Solution 2.

Computing the product of sines

In this section we show one way how to evaluate the product $\prod_{k=1}^6 \sin \frac{k\pi}7 = \prod_{k=1}^3 (\sin \frac{k\pi}7)^2$.

Let $\omega_k = \cos \frac{2k\pi}7 + i\sin \frac{2k\pi}7$. The numbers $1,\omega_1,\omega_2,\dots,\omega_6$ are the $7$-th complex roots of unity. In other words, these are the roots of the polynomial $x^7-1$. Then the numbers $\omega_1,\omega_2,\dots,\omega_6$ are the roots of the polynomial $\frac{x^7-1}{x-1} = x^6+x^5+\cdots+x+1$.

We just proved the identity $\prod_{k=1}^6 (x - \omega_k) = x^6+x^5+\cdots+x+1$. Substitute $x=1$. The right hand side is obviously equal to $7$. Let's now examine the left hand side. We have:

\begin{align*} (1-\omega_k)(1-\omega_{7-k})=|1-\omega_k|^2 & = \left( 1-\cos \frac{2k\pi}7 \right)^2 + \left( \sin \frac{2k\pi}7 \right)^2 \\ & = 2-2\cos \frac{2k\pi}7 \\ & = 2-2 \left( 1 - 2 \left( \sin \frac{k\pi}7 \right)^2 \right) \\ & = 4\left( \sin \frac{k\pi}7 \right)^2 \end{align*}

Therefore the size of the left hand side in our equation is $\prod_{k=1}^3 4 (\sin \frac{k\pi}7)^2 = 2^6 \prod_{k=1}^3 (\sin \frac{k\pi}7)^2$. As the right hand side is $7$, we get that $\prod_{k=1}^3 (\sin \frac{k\pi}7)^2 = \frac{7}{2^6}$.

Solution 4 (Product of Sines)

Lemma 1: A chord $ab$ of a circle with center $O$ and radius $r$ has length $2r\sin\left(\dfrac{\angle AOB}{2}\right)$.

Proof: Denote $H$ as the projection from $O$ to line $AB$. Then, by definition, $HA=HB=r\sin\left(\dfrac{\angle AOB}{2}\right)$. Thus, $AB = 2r\sin\left(\dfrac{\angle AOB}{2}\right)$, which concludes the proof.

Lemma 2: $\prod_{k=1}^{n-1} \sin \dfrac{k\pi}{n} = \dfrac{n}{2^{n-1}}$

Proof: Let $w=\text{cis}\;\dfrac{\pi}{n}$. Thus, \[\prod_{k=1}^{n-1} \sin \dfrac{k\pi}{n} = \prod_{k=1}^{n-1} \dfrac{w^k-w^{-k}}{2i} = \dfrac{w^{\frac{n(n-1)}{2}}}{(2i)^{n-1}}\prod_{k=1}^{n-1} (1-w^{-2k}) = \dfrac{1}{2^{n-1}}\prod_{k=1}^{n-1} (1-w^{-2k})\] Since, $w^{-2k}$ are just the $n$th roots of unity excluding $1$, by Vieta's, $\prod_{k=1}^{n-1} \sin \dfrac{k\pi}{n}=\dfrac{1}{2^{n-1}}\prod_{k=1}^{n-1} (1-w^{-2k}) = \dfrac{n}{2^{n-1}}$, thus completing the proof.

By Lemma 1, the length $AC_k=2r\sin\dfrac{k\pi}{14}$ and similar lengths apply for $BC_k$. Now, the problem asks for $\left(\prod_{k=1}^6 \left(4\sin\dfrac{k\pi}{14}\right)\right)^2$. This can be rewritten, due to $\sin \theta = \sin (\pi-\theta)$, as $\prod_{k=1}^6 \left(4\sin\dfrac{k\pi}{14}\right) \cdot \prod_{k=8}^{13} \left(4\sin\dfrac{k\pi}{14}\right) = \dfrac{1}{\sin \dfrac{7\pi}{14}}\cdot \prod_{k=1}^{13} \left(4\sin\dfrac{k\pi}{14}\right) = \prod_{k=1}^{13} \left(4\sin\dfrac{k\pi}{14}\right).$ By Lemma 2, this furtherly boils down to $4^{12}\cdot \dfrac{14}{2^{13}} = 7\cdot 2^{12} = \boxed{672} \; \text{(mod }1000\text{)}$

~Solution by sml1809


Video Solution

https://youtu.be/TrKxzgR7V8U?si=FFOBCJxjGrg9sWGC

~MathProblemSolvingSkills.com


See Also

2009 AIME II (Problems • Answer Key • Resources)
Preceded by
Problem 12 		Followed by
Problem 14
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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2009_AIME_II_Problems/Problem_13&oldid=228917"