Difference between revisions of "1990 AIME Problems/Problem 10"
m (→Solution 3) |
m (→Solution 1) |
||
Line 7: | Line 7: | ||
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>. |
=== Solution 2 === | === Solution 2 === |
Revision as of 12:07, 3 August 2020
Problem
The sets and are both sets of complex roots of unity. The set is also a set of complex roots of unity. How many distinct elements are in ?
Solution
Solution 1
The least common multiple of and is , so define . We can write the numbers of set as and of set as . can yield at most different values. All solutions for will be in the form of .
and are relatively prime, and by the Chicken McNugget Theorem, for two relatively prime integers , the largest number that cannot be expressed as the sum of multiples of is . For , this is ; however, we can easily see that the numbers to can be written in terms of . Since the exponents are of roots of unities, they reduce , so all numbers in the range are covered. Thus the answer is .
Solution 2
The 18 and 48th roots of can be found by De Moivre's Theorem. They are and respectively, where and and are integers from to and to , respectively.
. Since the trigonometric functions are periodic every , there are at most distinct elements in . As above, all of these will work.
Solution 3
The values in polar form will be and . Multiplying these gives . Then, we get , , , ,
up to .
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.