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 3)
(→‎Solution 1)
 
(9 intermediate revisions by 5 users not shown)
Line 2: Line 2:
 
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>?
 
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 1 ===
 
=== 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>.  
 
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>.
+
<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 ===
 
=== Solution 2 ===
Line 13: Line 15:
  
 
<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.
 
<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 ===
 
=== 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 (lcm(55,360)) \implies \frac{3960 \cdot 2}{55}=144</math>.
+
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 ==
 
== See also ==

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

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

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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1990_AIME_Problems/Problem_10&oldid=196410"