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

Revision as of 20:55, 6 December 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}$ .

$8$ and $3$ are relatively prime, and it is well known that 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 $\text{mod} 144$ , so all numbers in the range are covered. Thus the answer is $\boxed{144}$ .

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.

@@ Line 5: / Line 5: @@
 == 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>. 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>.
+<math>8</math> and <math>3</math> are relatively prime, and it is well known that 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>\text{mod} 144</math>, so all numbers in the range are covered. Thus the answer is <math>\boxed{144}</math>.
 === Solution 2 ===

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

Page

Toolbox

Search