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

Latest revision as of 03:47, 4 August 2023

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

Comment of S1

Using Chicken McNugget Theorem and the property of complex numbers for reasoning is sharp, but note that the Frobenius Number is only constrained to positive integer pairs. Please check on "Comment of S2" below to see how to use Diophantine equation to make a simple deduction. ~ Will_Dai

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.

Comment on S2

By the property of Diophantine equation, given a problem to find integers x and y so that ax + by = c for some integer constants a, b, c: if gcd(a, b) = 1, then any arbitrary integer c could by formed with some combination of integers (x, y). Double checking the constraints of k_1 and k_2, we realize that all integers of [0, 143] can be formed by 8 * k1 + 3 * k2, yielding the answer of 144. ~Will_Dai

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$ , $...$ up to $3960$ $(\text{lcm}(55,360)) \implies \frac{3960 \cdot 2}{55}=\boxed{144}$ .

Video Solution!

https://www.youtube.com/watch?v=hdamWTu_F94

@@ Line 1: / Line 1: @@
-{{empty}}
 == 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>?
 == 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>.
+==== Comment of S1 ====
+Using [[Chicken McNugget Theorem]] and the property of complex numbers for reasoning is sharp, but note that the Frobenius Number is only constrained to positive integer pairs. Please check on "Comment of S2" below to see how to use [[Diophantine equation]] to make a simple deduction. ~ Will_Dai
+=== 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.
+==== Comment on S2 ====
+By the property of [[Diophantine equation]], given a problem to find integers x and y so that ax + by = c for some integer constants a, b, c: if gcd(a, b) = 1, then any arbitrary integer c could by formed with some combination of integers (x, y). Double checking the constraints of k_1 and k_2, we realize that all integers of [0, 143] can be formed by 8 * k1 + 3 * k2, yielding the answer of 144.
+~Will_Dai
+=== 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>...</math> up to <math>3960</math> <math>(\text{lcm}(55,360)) \implies \frac{3960 \cdot 2}{55}=\boxed{144}</math>.
+== Video Solution! ==
+https://www.youtube.com/watch?v=hdamWTu_F94
 == See also ==
-* [[1990 AIME Problems]]
+{{AIME box|year=1990|num-b=9|num-a=11}}
+[[Category:Intermediate Algebra Problems]]
+{{MAA Notice}}

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