Difference between revisions of "1997 AIME Problems/Problem 14"

Latest revision as of 14:55, 16 November 2024

Problem

Let $v$ and $w$ be distinct, randomly chosen roots of the equation $z^{1997}-1=0$ . Let $\frac{m}{n}$ be the probability that $\sqrt{2+\sqrt{3}}\le\left|v+w\right|$ , where $m$ and $n$ are relatively prime positive integers. Find $m+n$ .

Solution

Solution 1

$z^{1997}=1=1(\cos 0 + i \sin 0)$

Define $\theta = 2\pi/1997$ . By De Moivre's Theorem the roots are given by

$z=\cos (k\theta) +i\sin(k\theta), \qquad k \in \{0,1,\ldots,1996\}$

Now, let $v$ be the root corresponding to $m\theta=2m\pi/1997$ , and let $w$ be the root corresponding to $n\theta=2n\pi/ 1997$ . Then $\begin{align*} |v+w|^2 &= \left(\cos(m\theta) + \cos(n\theta)\right)^2 + \left(\sin(m\theta) + \sin(n\theta)\right)^2 \\ &= 2 + 2\cos\left(m\theta\right)\cos\left(n\theta\right) + 2\sin\left(m\theta\right)\sin\left(n\theta\right) \end{align*}$ The cosine difference identity simplifies that to $|v+w|^2 = 2+2\cos((m-n)\theta)$

We need $|v+w|^2 \ge 2+\sqrt{3}$ , which simplifies to $\cos((m-n)\theta) \ge \frac{\sqrt{3}}{2}.$ Hence, $-\frac{\pi}{6} \le (m-n) \theta \le \frac{\pi}{6},$ or alternatively, $|m - n| \theta \le \frac{\pi}{6}.$

Recall that $\theta=\frac{2\pi}{1997}.$ Thus, $|m - n| \le \frac{\pi}{6} \cdot \frac{1997}{2 \pi} = \left\lfloor \frac{1997}{12} \right\rfloor =166.$

Therefore, $m$ and $n$ cannot be more than $166$ away from each other. This means that for a given value of $m$ , there are $332$ values for $n$ that satisfy the inequality; $166$ of them $> m$ , and $166$ of them $< m$ ( $m \neq n$ since the problem says that $m$ and $n$ are distinct). Since $m$ and $n$ must be distinct, $n$ can have $1996$ total possible values for each value of $m$ . Therefore, the probability is $\frac{332}{1996}=\frac{83}{499}$ . The answer is then $499+83=\boxed{582}$ .

Solution 2

The solutions of the equation $z^{1997} = 1$ are the $1997$ th roots of unity and are equal to $\text{cis}(\theta_k)$ , where $\theta_k = \tfrac {2\pi k}{1997}$ for $k = 0,1,\ldots,1996.$ Thus, they are located at uniform intervals on the unit circle in the complex plane.

The quantity $|v+w|$ is unchanged upon rotation around the origin, so, WLOG, we can assume $v=1$ after rotating the axis till $v$ lies on the real axis. Let $w=\text{cis}(\theta_k)$ . Since $w\cdot \overline{w}=|w|^2=1$ and $w+\overline{w}=2\text{Re}(w) = 2\cos\theta_k$ , we have $|v + w|^2 = (1+w)(1+\overline{w}) = 2+2\cos\theta_k$ We want $|v + w|^2\ge 2 + \sqrt {3}.$ From what we just obtained, this is equivalent to $\cos\theta_k\ge \frac {\sqrt {3}}2 \qquad \Leftrightarrow \qquad -\frac {\pi}6\le \theta_k \le \frac {\pi}6$ which is satisfied by $k = 166,165,\ldots, - 165, - 166$ (we don't include 0 because that corresponds to $v$ ). So out of the $1996$ possible $k$ , $332$ work. Thus, $m/n = 332/1996 = 83/499.$ So our answer is $83 + 499 = \boxed{582}.$

Solution 3

We can solve a geometrical interpretation of this problem.

Without loss of generality, let $w = 1$ . We are now looking for a point exactly one unit away from $w$ such that the point is at least $\sqrt{2 + \sqrt{3}}$ units away from the origin. Note that the "boundary" condition is when the point will be exactly $\sqrt{2+\sqrt{3}}$ units away from the origin; these points will be the intersections of the circle centered at $(1,0)$ with radius $1$ and the circle centered at $(0,0)$ with radius $\sqrt{2+\sqrt{3}}$ . The equations of these circles are $(x-1)^2 + y^2 = 1$ and $x^2 + y^2 = 2 + \sqrt{3}$ . Solving for $x$ yields $x = 1 + \frac{\sqrt{3}}{2}$ . Clearly, this means that the real part of $v$ is greater than $\frac{\sqrt{3}}{2}$ . Solving, we note that $332$ possible $v$ s exist, meaning that $\frac{m}{n} = \frac{332}{1996} = \frac{83}{499}$ . Therefore, the answer is $83 + 499 = \boxed{582}$ .

Solution 4

Since $z^{1997}=1$ , the roots will have magnitude $1$ . Thus, the roots can be written as $\cos(\theta)+i\sin(\theta)$ and $\cos(\omega)+i\sin(\omega)$ for some angles $\theta$ and $\omega$ . We rewrite the requirement as $\sqrt{2+\sqrt3}\le|\cos(\theta)+\cos(\omega)+i\sin(\theta)+i\sin(\omega)|$ , which can now be easily manipulated to $2+\sqrt{3}\le(\cos(\theta)+\cos(\omega))^2+(\sin(\theta)+\sin(\omega))^2$ .

WLOG, let $\theta = 0$ . Thus, our inequality becomes $2+\sqrt{3}\le(1+\cos(\omega))^2+(\sin(\omega))^2$ , $2+\sqrt{3}\le2+2\cos(\omega)$ , and finally $\cos(\omega)\ge\frac{\sqrt{3}}{2}$ . Obviously, $\cos(\frac{\pi}{6})=\frac{\sqrt{3}}{2}$ , and thus it follows that, on either side of a given point, $\frac{1997}{12}\approx166$ points will work. The probability is $\frac{166\times2}{1996} = \frac{83}{499}$ , and thus our requested sum is $\boxed{582}$ ~SigmaPiE

@@ Line 1: / Line 1: @@
 == Problem ==
-Let <math>\displaystyle v</math> and <math>\displaystyle w</math> be distinct, randomly chosen roots of the equation <math>\displaystyle z^{1997}-1=0</math>.  Let <math>\displaystyle \frac{m}{n}</math> be the probability that <math>\displaystyle\sqrt{2+\sqrt{3}}\le\left|v+w\right|</math>, where <math>\displaystyle m</math> and <math>\displaystyle n</math> are relatively prime positive integers.  Find <math>\displaystyle m+n</math>.
+Let <math>v</math> and <math>w</math> be distinct, randomly chosen [[root]]s of the equation <math>z^{1997}-1=0</math>.  Let <math>\frac{m}{n}</math> be the [[probability]] that <math>\sqrt{2+\sqrt{3}}\le\left|v+w\right|</math>, where <math>m</math> and <math>n</math> are [[relatively prime]] [[positive]] [[integer]]s.  Find <math>m+n</math>.
+__TOC__
 == Solution ==
-The solution requires the use of Euler's formula:
+=== Solution 1 ===
+:<math>z^{1997}=1=1(\cos 0 + i \sin 0)</math>
-<math>\displaystyle e^{i\theta}=\cos(\theta)+i\sin(\theta)</math>
+Define <math>\theta = 2\pi/1997</math>. By [[De Moivre's Theorem]] the roots are given by
-If <math>\displaystyle \theta=2\pi ik</math>, where k is any constant, the equation reduces to:
+:<math>z=\cos (k\theta) +i\sin(k\theta), \qquad k \in \{0,1,\ldots,1996\}</math>
-<math>\begin{eqnarray*}
-e^{2\pi ik}&=&\cos(2\pi k)+i\sin(2\pi k)\\
+Now, let <math>v</math> be the root corresponding to <math>m\theta=2m\pi/1997</math>, and let <math>w</math> be the root corresponding to <math>n\theta=2n\pi/ 1997</math>. Then
-&=&1+0i\\
+<cmath>\begin{align*}
-&=&1+0\\
+|v+w|^2 &= \left(\cos(m\theta) + \cos(n\theta)\right)^2 + \left(\sin(m\theta) + \sin(n\theta)\right)^2 \\
-&=&1\\
+&= 2 + 2\cos\left(m\theta\right)\cos\left(n\theta\right) + 2\sin\left(m\theta\right)\sin\left(n\theta\right)
-z^{1997}-1&=&0\\
+\end{align*}</cmath>
-z^{1997}&=&1\\
+The [[Trigonometric identities|cosine difference identity]] simplifies that to
-z^{1997}&=&e^{2\pi ik}\\
+<cmath>|v+w|^2 = 2+2\cos((m-n)\theta) </cmath>
-z&=&e^{\frac{2\pi ik}{1997}}
-\end{eqnarray*}<math>
+We need <math>|v+w|^2 \ge 2+\sqrt{3}</math>, which simplifies to <cmath>\cos((m-n)\theta) \ge \frac{\sqrt{3}}{2}.</cmath> Hence, <math>-\frac{\pi}{6} \le (m-n) \theta \le \frac{\pi}{6},</math> or alternatively, <math>|m - n| \theta \le \frac{\pi}{6}.</math>
+Recall that <math>\theta=\frac{2\pi}{1997}.</math> Thus, <cmath>|m - n| \le \frac{\pi}{6} \cdot \frac{1997}{2 \pi} = \left\lfloor \frac{1997}{12} \right\rfloor =166.</cmath>
+Therefore, <math>m</math> and <math>n</math> cannot be more than <math>166</math> away from each other.  This means that for a given value of <math>m</math>, there are <math>332</math> values for <math>n</math> that satisfy the inequality; <math>166</math> of them <math>> m</math>, and <math>166</math> of them <math>< m</math> (<math>m \neq n</math> since the problem says that <math>m</math> and <math>n</math> are distinct).  Since <math>m</math> and <math>n</math> must be distinct, <math>n</math> can have <math>1996</math> total possible values for each value of <math>m</math>.  Therefore, the probability is <math>\frac{332}{1996}=\frac{83}{499}</math>.  The answer is then <math>499+83=\boxed{582}</math>.
+=== Solution 2 ===
+The solutions of the equation <math>z^{1997} = 1</math> are the <math>1997</math>th [[roots of unity]] and are equal to <math>\text{cis}(\theta_k)</math>, where <math>\theta_k = \tfrac {2\pi k}{1997}</math> for <math>k = 0,1,\ldots,1996.</math> Thus, they are located at uniform intervals on the unit circle in the complex plane.
+The quantity <math>|v+w|</math> is unchanged upon rotation around the origin, so, WLOG, we can assume <math>v=1</math> after rotating the axis till <math>v</math> lies on the real axis. Let <math>w=\text{cis}(\theta_k)</math>. Since <math>w\cdot \overline{w}=|w|^2=1</math> and <math>w+\overline{w}=2\text{Re}(w) = 2\cos\theta_k</math>, we have <cmath>|v + w|^2  =  (1+w)(1+\overline{w}) = 2+2\cos\theta_k</cmath>
+We want <math>|v + w|^2\ge 2 + \sqrt {3}.</math>  From what we just obtained, this is equivalent to <cmath>\cos\theta_k\ge \frac {\sqrt {3}}2 \qquad \Leftrightarrow \qquad -\frac {\pi}6\le \theta_k \le  \frac {\pi}6</cmath> which is satisfied by <math>k = 166,165,\ldots, - 165, - 166</math> (we don't include 0 because that corresponds to <math>v</math>).  So out of the <math>1996</math> possible <math>k</math>, <math>332</math> work.  Thus, <math>m/n = 332/1996 = 83/499.</math>  So our answer is <math>83 + 499 = \boxed{582}.</math>
+=== Solution 3 ===
+We can solve a geometrical interpretation of this problem.
+Without loss of generality, let <math>w = 1</math>. We are now looking for a point exactly one unit away from <math>w</math> such that the point is at least <math>\sqrt{2 + \sqrt{3}}</math> units away from the origin. Note that the "boundary" condition is when the point will be exactly <math>\sqrt{2+\sqrt{3}}</math> units away from the origin; these points will be the intersections of the circle centered at <math>(1,0)</math> with radius <math>1</math> and the circle centered at <math>(0,0)</math> with radius <math>\sqrt{2+\sqrt{3}}</math>. The equations of these circles are <math>(x-1)^2 + y^2 = 1</math> and <math>x^2 + y^2 = 2 + \sqrt{3}</math>. Solving for <math>x</math> yields <math>x = 1 + \frac{\sqrt{3}}{2}</math>. Clearly, this means that the real part of <math>v</math> is greater than <math>\frac{\sqrt{3}}{2}</math>. Solving, we note that <math>332</math> possible <math>v</math>s exist, meaning that <math>\frac{m}{n} = \frac{332}{1996} = \frac{83}{499}</math>. Therefore, the answer is <math>83 + 499 = \boxed{582}</math>.
+=== Solution 4 ===
+Since <math>z^{1997}=1</math>, the roots will have magnitude <math>1</math>. Thus, the roots can be written as <math>\cos(\theta)+i\sin(\theta)</math> and <math>\cos(\omega)+i\sin(\omega)</math> for some angles <math>\theta</math> and <math>\omega</math>. We rewrite the requirement as <math>\sqrt{2+\sqrt3}\le|\cos(\theta)+\cos(\omega)+i\sin(\theta)+i\sin(\omega)|</math>, which can now be easily manipulated to <math>2+\sqrt{3}\le(\cos(\theta)+\cos(\omega))^2+(\sin(\theta)+\sin(\omega))^2</math>.
+WLOG, let <math>\theta = 0</math>. Thus, our inequality becomes <math>2+\sqrt{3}\le(1+\cos(\omega))^2+(\sin(\omega))^2</math>, <math>2+\sqrt{3}\le2+2\cos(\omega)</math>, and finally <math>\cos(\omega)\ge\frac{\sqrt{3}}{2}</math>. Obviously, <math>\cos(\frac{\pi}{6})=\frac{\sqrt{3}}{2}</math>, and thus it follows that, on either side of a given point, <math>\frac{1997}{12}\approx166</math> points will work. The probability is <math>\frac{166\times2}{1996} = \frac{83}{499}</math>, and thus our requested sum is <math>\boxed{582}</math>
+~SigmaPiE
 == See also ==
-* [[1997 AIME Problems]]</math>
+{{AIME box|year=1997|num-b=13|num-a=15}}
+[[Category:Intermediate Algebra Problems]]
+{{MAA Notice}}

1997 AIME (Problems • Answer Key • Resources)
Preceded by Problem 13	Followed by Problem 15
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

Page

Toolbox

Search