Sunday, March 11, 2007

Da Roots. Topic: Algebra/Complex Numbers Level: AIME.

Problem: (2007 Mock AIME 6 - #7) Let $ P_n(x) = 1+x+x^2+\cdots+x^n $ and $ Q_n(x) = P_1 \cdot P_2 \cdots P_n $ for all integers $ n \ge 1 $. How many more distinct complex roots does $ Q_{1004} $ have than $ Q_{1003} $?

Solution: Well, $ P_n(x) $ is familiar. Rewrite as

$ P_n(x) = \frac{x^{n+1}-1}{x-1} $,

i.e. the $ (n+1)-$th roots of unity except $ 1 $. Since $ Q_{1004} $ just contains a $ P_{1004} $ term that $ Q_{1003} $ doesn't have, we only need to think about that term in relation to the previous ones. So we want to find out how many of the $ 1004+1 = 1005 $th roots of unity are not $ k $-th roots of unity for any $ k < 1005 $. Well, recalling that any $ k $-th root of unity can be written as

$ e^{2 \pi i \frac{p}{k}} = \cos{\left(2 \pi \frac{p}{k}\right)}+i \sin{\left(2 \pi \frac{p}{k}\right)} $

for $ p = 0, 1, \ldots, k-1 $, it remains to find the number of $ p $ such that $ \frac{p}{1005} $ does not reduce. But this, of course, is simply $ \phi(1005) = 1005\left(1-\frac{1}{3}\right)\left(1-\frac{1}{5}\right)\left(1-\frac{1}{67}\right) = 2 \cdot 4 \cdot 66 = 528 $. QED.

--------------------

Comment: Definitely one of my favorite problems on the test because it has a really nice and clean solution once you see it. And it wasn't too difficult to see either; combining a little knowledge of roots of unity with a little knowledge of the $ \phi $ function made it a good problem. Furthermore, it offers the nice generalization that

$ Q_n $ has $ \phi(n+1) $ more distinct roots than $ Q_{n-1} $.

--------------------

Practice Problem: (2007 Mock AIME 6 - #8) A sequence of positive reals is defined by $ a_0 = x $, $ a_1 = y $, and $ a_n \cdot a_{n+2} = a_{n+1} $ for all integers $ n \ge 0 $. Given that $ a_{2007}+a_{2008} = 3 $ and $ a_{2007} \cdot a_{2008} = \frac{1}{3} $, find $ x^3+y^3 $.

1 comment:

  1. The solution's immediate with cyclotomic polynomials =D

    ReplyDelete