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 "1990 AIME Problems/Problem 10"

m (→‎Solution 2: missed 2)
(category)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
−
The sets <math>\displaystyle A = \{z : z^{18} = 1\}</math> and <math>\displaystyle B = \{w : w^{48} = 1\}</math> are both sets of complex roots of unity.  The set <math>C = \{zw : z \in A ~ \mbox{and} ~ w \in B\}</math> is also a set of complex roots of unity.  How many distinct elements are in <math>C_{}^{}</math>?
+
The sets <math>A = \{z : z^{18} = 1\}</math> and <math>B = \{w : w^{48} = 1\}</math> are both sets of complex roots of unity.  The set <math>C = \{zw : z \in A ~ \mbox{and} ~ w \in B\}</math> is also a set of complex roots of unity.  How many distinct elements are in <math>C_{}^{}</math>?
  
 
__TOC__
 
__TOC__
 
== Solution ==
 
== Solution ==
 
=== Solution 1 ===
 
=== Solution 1 ===
−
The [[least common multiple]] of <math>18</math> and <math>48</math> is <math>144</math>, so define <math>\displaystyle n = e^{2\pi i/144}</math>. We can write the numbers of set <math>A</math> as <math>\displaystyle \{n^8, n^{16}, \ldots n^{144}\}</math> and of set <math>B</math> as <math>\displaystyle \{n^3, n^6, \ldots n^{144}\}</math>. <math>n^x</math> can yield at most <math>144</math> different values. All solutions for <math>zw</math> will be in the form of <math>n^{8k_1 + 3k_2}</math>. Since <math>8</math> and <math>3</math> are different <math>\pmod{3}</math>, all <math>144</math> distinct elements will be covered.
+
The [[least common multiple]] of <math>18</math> and <math>48</math> is <math>144</math>, so define <math>n = e^{2\pi i/144}</math>. We can write the numbers of set <math>A</math> as <math>\{n^8, n^{16}, \ldots n^{144}\}</math> and of set <math>B</math> as <math>\{n^3, n^6, \ldots n^{144}\}</math>. <math>n^x</math> can yield at most <math>144</math> different values. All solutions for <math>zw</math> will be in the form of <math>n^{8k_1 + 3k_2}</math>. Since <math>8</math> and <math>3</math> are different <math>\pmod{3}</math>, all <math>144</math> distinct elements will be covered.
  
 
=== Solution 2 ===
 
=== Solution 2 ===
Line 15: Line 15:
 
{{AIME box|year=1990|num-b=9|num-a=11}}
 
{{AIME box|year=1990|num-b=9|num-a=11}}
  
−
[[Category:Intermediate Complex Numbers Problems]]
+
[[Category:Intermediate Algebra Problems]]

Revision as of 21:13, 30 November 2007

Problem

The sets $A = \{z : z^{18} = 1\}$ and $B = \{w : w^{48} = 1\}$ are both sets of complex roots of unity. The set $C = \{zw : z \in A ~ \mbox{and} ~ w \in B\}$ is also a set of complex roots of unity. How many distinct elements are in $C_{}^{}$?

Solution

Solution 1

The least common multiple of $18$ and $48$ is $144$, so define $n = e^{2\pi i/144}$. We can write the numbers of set $A$ as $\{n^8, n^{16}, \ldots n^{144}\}$ and of set $B$ as $\{n^3, n^6, \ldots n^{144}\}$. $n^x$ can yield at most $144$ different values. All solutions for $zw$ will be in the form of $n^{8k_1 + 3k_2}$. Since $8$ and $3$ are different $\pmod{3}$, all $144$ distinct elements will be covered.

Solution 2

The 18th and 48th roots of $1$ can be found using De Moivre's Theorem. They are $cis \left(\frac{2\pi k_1}{18}\right)$ and $cis \left(\frac{2\pi k_2}{48}\right)$ respectively, where $cis \theta = \cos \theta + i \sin \theta$ and $k_1$ and $k_2$ are integers from 0 to 17 and 0 to 47, respectively.

$zw = cis \left(\frac{\pi k_1}{9} + \frac{\pi k_2}{24}\right) = cis \left(\frac{8\pi k_1 + 3 \pi k_2}{72}\right)$. Since the trigonometric functions are periodic every $2\pi$, there are at most $72 \cdot 2 = 144$ distinct elements in $C$. As above, all of these will work.

See also

1990 AIME (Problems • Answer Key • Resources)
Preceded by
Problem 9 		Followed by
Problem 11
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1990_AIME_Problems/Problem_10&oldid=20401"