AIME 1990 · 第 10 题

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 $8k_1 + 3k_2$, 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