Difference between revisions of "1990 AIME Problems/Problem 10"

m (Solution 3)
(16 intermediate revisions by 8 users not shown)
Line 1: Line 1:
{{empty}}
 
 
== Problem ==
 
== Problem ==
 +
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__
 
== Solution ==
 
== Solution ==
{{solution}}
+
=== Solution 1 ===
 +
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>.
 +
 
 +
<math>8</math> and <math>3</math> are relatively prime, and by the [[Chicken McNugget Theorem]], for two relatively prime integers <math>a,b</math>, the largest number that cannot be expressed as the sum of multiples of <math>a,b</math> is <math>a \cdot b - a - b</math>. For <math>3,8</math>, this is <math>13</math>; however, we can easily see that the numbers <math>145</math> to <math>157</math> can be written in terms of <math>3,8</math>. Since the exponents are of roots of unities, they reduce <math>\mod{144}</math>, so all numbers in the range are covered. Thus the answer is <math>\boxed{144}</math>.
 +
 
 +
=== Solution 2 ===
 +
The 18 and 48th roots of <math>1</math> can be found by [[De Moivre's Theorem]]. They are <math>\text{cis}\,\left(\frac{2\pi k_1}{18}\right)</math> and <math>\text{cis}\,\left(\frac{2\pi k_2}{48}\right)</math> respectively, where <math>\text{cis}\,\theta = \cos \theta + i \sin \theta</math> and <math>k_1</math> and <math>k_2</math> are integers from <math>0</math> to <math>17</math> and <math>0</math> to <math>47</math>, respectively.
 +
 
 +
<math>zw = \text{cis}\,\left(\frac{\pi k_1}{9} + \frac{\pi k_2}{24}\right) = \text{cis}\,\left(\frac{8\pi k_1 + 3 \pi k_2}{72}\right)</math>. Since the [[trigonometry|trigonometric]] functions are [[periodic function|periodic]] every <math>2\pi</math>, there are at most <math>72 \cdot 2 = \boxed{144}</math> distinct elements in <math>C</math>. As above, all of these will work.
 +
 
 +
=== Solution 3 ===
 +
The values in polar form will be <math>(1, 20x)</math> and <math>(1, 7.5x)</math>. Multiplying these gives <math>(1, 27.5x)</math>. Then, we get <math>27.5</math>, <math>55</math>, <math>82.5</math>, <math>110</math>, <math>\cdots</math>
 +
 
 +
up to <math>3960</math> <math>(lcm(55,360)) \implies \frac{3960 \cdot 2}{55}=\boxed{144}</math>.
 +
 
 
== See also ==
 
== See also ==
* [[1990 AIME Problems]]
+
{{AIME box|year=1990|num-b=9|num-a=11}}
 +
 
 +
[[Category:Intermediate Algebra Problems]]
 +
{{MAA Notice}}

Revision as of 13:08, 3 August 2020

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}$.

$8$ and $3$ are relatively prime, and by the Chicken McNugget Theorem, for two relatively prime integers $a,b$, the largest number that cannot be expressed as the sum of multiples of $a,b$ is $a \cdot b - a - b$. For $3,8$, this is $13$; however, we can easily see that the numbers $145$ to $157$ can be written in terms of $3,8$. Since the exponents are of roots of unities, they reduce $\mod{144}$, so all numbers in the range are covered. Thus the answer is $\boxed{144}$.

Solution 2

The 18 and 48th roots of $1$ can be found by De Moivre's Theorem. They are $\text{cis}\,\left(\frac{2\pi k_1}{18}\right)$ and $\text{cis}\,\left(\frac{2\pi k_2}{48}\right)$ respectively, where $\text{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 = \text{cis}\,\left(\frac{\pi k_1}{9} + \frac{\pi k_2}{24}\right) = \text{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 = \boxed{144}$ distinct elements in $C$. As above, all of these will work.

Solution 3

The values in polar form will be $(1, 20x)$ and $(1, 7.5x)$. Multiplying these gives $(1, 27.5x)$. Then, we get $27.5$, $55$, $82.5$, $110$, $\cdots$

up to $3960$ $(lcm(55,360)) \implies \frac{3960 \cdot 2}{55}=\boxed{144}$.

See also

1990 AIME (ProblemsAnswer KeyResources)
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

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png