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 "Mock AIME 6 2006-2007 Problems/Problem 7"
 
(13 intermediate revisions by the same user not shown)
Line 4: Line 4:
 
==Solution==
 
==Solution==
  
−
The roots of <math>P_n(x)</math> will be in the form <math>x=e^{\frac{2\pi k}{n+1}}</math> for <math>k=1,2,\cdots,n</math> with the only real solution when <math>n</math> is odd and <math>k=\frac{n+1}{2}</math> and the rest are complex.
+
The roots of <math>P_n(x)</math> will be in the form <math>x=e^{\frac{k}{n+1}2\pi i}</math> for <math>k=1,2,\cdots,n</math> with the only real solution when <math>n</math> is odd and <math>k=\frac{n+1}{2}</math> and the rest are complex.
  
−
Therefore each <math>P_n(x)</math> will have <math>n</math> distinct complex roots when <math>n</math> is even and <math>n-1</math> distinct complex roots when <math>n</math> is odd.
+
Therefore, each <math>P_n(x)</math> will have <math>n</math> distinct complex roots when <math>n</math> is even and <math>n-1</math> distinct complex roots when <math>n</math> is odd.
 +
 
 +
The roots of <math>Q_n(x)</math> will be all of the roots of <math>P_1,P_2,\cdots, P_n</math> which will include several repeated roots.
 +
 
 +
To get how many more complex roots does <math>Q_{1004}</math> have than <math>Q_{1003}</math> that will be the number of complex roots of <math>P_{1004}</math>.
 +
 
 +
But to get how many more '''distinct''' complex roots, we must subtract the complex roots of <math>P_{1004}</math> that can be found in <math>Q_{1003}</math>
 +
 
 +
complex roots of <math>P_{1004}:\; x=e^{\frac{1}{1005}2\pi i},e^{\frac{2}{1005}2\pi i},e^{\frac{3}{1005}2\pi i},\cdots,e^{\frac{1004}{1005}2\pi i}</math> for a total of <math>\textbf{1004}</math> complex roots.
 +
 
 +
Now we subtract the common complex roots of <math>P_{1004}</math> with <math>Q_{1003}</math> by finding how many reducible fractions are there in <math>\frac{k}{1005}</math> for <math>k=1,2,\cdots,1005</math>
 +
 
 +
Since <math>1005=(3)(5)(67)</math> then <math>\frac{k}{1005}</math> is reducible when <math>k \equiv 0\;(mod\;3)</math> or <math>k \equiv 0\;(mod\;5)</math> or <math>k \equiv 0\;(mod\;67)</math>
 +
 
 +
<math>k \equiv 0\;(mod\;3):</math>
 +
 
 +
<math>3, 6, 9, 12, 15,\cdots, 1002</math> gives '''334''' terms
 +
 
 +
<math>k \equiv 0\;(mod\;5):</math>
 +
 
 +
<math>5, 10, 15, 20, 25,\cdots, 1000</math> gives '''200''' terms
 +
 
 +
But we subtract the repeated terms in the 5 sequence that are also a multiple of 3:
 +
 
 +
<math>15, 30,\cdots,990</math> which is '''66''' terms
 +
 
 +
<math>k \equiv 0\;(mod\;67):</math>
 +
 
 +
<math>67, 134, 201,\cdots, 928</math> gives '''14''' terms 
 +
 
 +
But we subtract the repeated terms in the 67 sequence that are also a multiple of 3 or 5:
 +
 
 +
<math>201, 402, 603, 804</math> and <math>335, 670</math> gives '''6''' terms.
 +
 
 +
Total terms to subtract: <math>334+200-66+14-6=\textbf{476}</math>
 +
 
 +
Therefore, the number of distinct complex that <math>Q_{1004}</math> have more than <math>Q_{1003}</math> is:
 +
 
 +
<math>1004-476=\boxed{528}</math> distinct complex roots that <math>Q_{1004}</math> have more than <math>Q_{1003}</math>
  
 
~Tomas Diaz. orders@tomasdiaz.com
 
~Tomas Diaz. orders@tomasdiaz.com
  
 
{{alternate solutions}}
 
{{alternate solutions}}

Latest revision as of 19:51, 26 November 2023

Problem

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

The roots of $P_n(x)$ will be in the form $x=e^{\frac{k}{n+1}2\pi i}$ for $k=1,2,\cdots,n$ with the only real solution when $n$ is odd and $k=\frac{n+1}{2}$ and the rest are complex.

Therefore, each $P_n(x)$ will have $n$ distinct complex roots when $n$ is even and $n-1$ distinct complex roots when $n$ is odd.

The roots of $Q_n(x)$ will be all of the roots of $P_1,P_2,\cdots, P_n$ which will include several repeated roots.

To get how many more complex roots does $Q_{1004}$ have than $Q_{1003}$ that will be the number of complex roots of $P_{1004}$.

But to get how many more distinct complex roots, we must subtract the complex roots of $P_{1004}$ that can be found in $Q_{1003}$

complex roots of $P_{1004}:\; x=e^{\frac{1}{1005}2\pi i},e^{\frac{2}{1005}2\pi i},e^{\frac{3}{1005}2\pi i},\cdots,e^{\frac{1004}{1005}2\pi i}$ for a total of $\textbf{1004}$ complex roots.

Now we subtract the common complex roots of $P_{1004}$ with $Q_{1003}$ by finding how many reducible fractions are there in $\frac{k}{1005}$ for $k=1,2,\cdots,1005$

Since $1005=(3)(5)(67)$ then $\frac{k}{1005}$ is reducible when $k \equiv 0\;(mod\;3)$ or $k \equiv 0\;(mod\;5)$ or $k \equiv 0\;(mod\;67)$

$k \equiv 0\;(mod\;3):$

$3, 6, 9, 12, 15,\cdots, 1002$ gives 334 terms

$k \equiv 0\;(mod\;5):$

$5, 10, 15, 20, 25,\cdots, 1000$ gives 200 terms

But we subtract the repeated terms in the 5 sequence that are also a multiple of 3:

$15, 30,\cdots,990$ which is 66 terms

$k \equiv 0\;(mod\;67):$

$67, 134, 201,\cdots, 928$ gives 14 terms

But we subtract the repeated terms in the 67 sequence that are also a multiple of 3 or 5:

$201, 402, 603, 804$ and $335, 670$ gives 6 terms.

Total terms to subtract: $334+200-66+14-6=\textbf{476}$

Therefore, the number of distinct complex that $Q_{1004}$ have more than $Q_{1003}$ is:

$1004-476=\boxed{528}$ distinct complex roots that $Q_{1004}$ have more than $Q_{1003}$

~Tomas Diaz. orders@tomasdiaz.com

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Mock_AIME_6_2006-2007_Problems/Problem_7&oldid=205972"