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 I 2012 Problems/Problem 15"

(Created page with "==Problem== Paula the Painter initially paints every complex number black. When Paula toggles a complex number, she paints it white if it was previously black, and black if it wa...")
 
m (→‎Solution)
 
(One intermediate revision by the same user not shown)
Line 4: Line 4:
 
==Solution==
 
==Solution==
 
First, note that <math>x^{2k}+x^k+1=(x^{3k}-1)/(x^k-1)</math>. Let <math>z_1,z_2,\dots,z_n</math> be the distinct complex numbers that were toggled, where <math>n</math> is a positive integer, and for each complex number <math>z</math>, let <math>t(z)</math> be the number of times <math>z</math> was toggled. Then, we have this relation:
 
First, note that <math>x^{2k}+x^k+1=(x^{3k}-1)/(x^k-1)</math>. Let <math>z_1,z_2,\dots,z_n</math> be the distinct complex numbers that were toggled, where <math>n</math> is a positive integer, and for each complex number <math>z</math>, let <math>t(z)</math> be the number of times <math>z</math> was toggled. Then, we have this relation:
−
  \begin{equation}\label{eq:product}
+
<cmath>
−
      \prod_{k=1}^{20}(x^{2k}+x^k+1)=\prod_{k=1}^{20}\frac{x^{3k}-1}{x^k-1}=\prod_{i=1}^n (x-z_i)^{t(z_i)}.
+
\prod_{k=1}^{20}(x^{2k}+x^k+1)=\prod_{k=1}^{20}\frac{x^{3k}-1}{x^k-1}=\prod_{i=1}^n (x-z_i)^{t(z_i)}.\tag{1}
−
  \end{equation}
+
</cmath>
  
 
The problem is equivalent to finding the number of complex numbers <math>z_i</math> such that <math>t(z_i)</math> is odd.
 
The problem is equivalent to finding the number of complex numbers <math>z_i</math> such that <math>t(z_i)</math> is odd.
−
 
+
 
−
We now focus on the second formula in \eqref{eq:product}. From this formula, we know that all of the <math>z_i</math> must be roots of unity. Furthermore, for each <math>z_i</math>, <math>t(z_i)</math> is the number of factors in the numerator that have <math>z_i</math> as a root minus the number of factors in the denominator that have <math>z_i</math> as a root, since no polynomial of the form <math>x^n-1</math> has a repeated root.
+
We now focus on the second formula in <math>(1)</math>. From this formula, we know that all of the <math>z_i</math> must be roots of unity. Furthermore, for each <math>z_i</math>, <math>t(z_i)</math> is the number of factors in the numerator that have <math>z_i</math> as a root minus the number of factors in the denominator that have <math>z_i</math> as a root, since no polynomial of the form <math>x^n-1</math> has a repeated root.
 
    
 
    
 
Now let <math>\zeta_n</math> denote a primitive <math>n</math>th root of unity. First, when <math>3\nmid n</math>, there are an equal number of factors in the numerator of the fraction as in the denominator of the fraction which have <math>\zeta_n</math> as a root, so <math>t(\zeta_n)=0</math> in this case.
 
Now let <math>\zeta_n</math> denote a primitive <math>n</math>th root of unity. First, when <math>3\nmid n</math>, there are an equal number of factors in the numerator of the fraction as in the denominator of the fraction which have <math>\zeta_n</math> as a root, so <math>t(\zeta_n)=0</math> in this case.
Line 16: Line 16:
 
We now consider the case when <math>3\mid n</math>. The numerator has <math>\lfloor 60/n\rfloor</math> factors with <math>\zeta_n</math> as a root, while the denominator has <math>\lfloor 20/n\rfloor</math> factors with <math>\zeta_n</math> as a root. Therefore, in this case, <math>t(\zeta_n)=\lfloor 60/n\rfloor-\lfloor 20/n\rfloor</math>. As there are <math>\phi(n)</math> primitive <math>n</math>th roots of unity for each <math>n</math>, every <math>n</math> with <math>t(\zeta_n)</math> odd will contribute <math>\phi(n)</math> to the sum. The table below shows the calculations for <math>n=3,6,9,\dots,60</math>.
 
We now consider the case when <math>3\mid n</math>. The numerator has <math>\lfloor 60/n\rfloor</math> factors with <math>\zeta_n</math> as a root, while the denominator has <math>\lfloor 20/n\rfloor</math> factors with <math>\zeta_n</math> as a root. Therefore, in this case, <math>t(\zeta_n)=\lfloor 60/n\rfloor-\lfloor 20/n\rfloor</math>. As there are <math>\phi(n)</math> primitive <math>n</math>th roots of unity for each <math>n</math>, every <math>n</math> with <math>t(\zeta_n)</math> odd will contribute <math>\phi(n)</math> to the sum. The table below shows the calculations for <math>n=3,6,9,\dots,60</math>.
 
    
 
    
−
  \begin{center}
+
<cmath>
−
      \begin{tabular}{cccc}
+
\begin{array}{cccc}
−
        \toprule
+
\hline
−
        <math>n</math> & <math>t(\zeta_n)=\lfloor 60/n\rfloor -\lfloor 20/n\rfloor</math> & Contribution\\
+
n & t(\zeta_n)=\lfloor 60/n\rfloor -\lfloor 20/n\rfloor & \text{Contribution}\\
−
        \midrule
+
\hline
−
        3 & 14 & 0\\
+
3 & 14 & 0\\
−
        6 & 7 & 2\\
+
6 & 7 & 2\\
−
        9 & 4 & 0\\
+
9 & 4 & 0\\
−
        12 & 4 & 0\\
+
12 & 4 & 0\\
−
        15 & 3 & 8\\
+
15 & 3 & 8\\
−
        18 & 2 & 0\\
+
18 & 2 & 0\\
−
        21 & 2 & 0\\
+
21 & 2 & 0\\
−
        24 & 2 & 0\\
+
24 & 2 & 0\\
−
        27 & 2 & 0\\
+
27 & 2 & 0\\
−
        30 & 2 & 0\\
+
30 & 2 & 0\\
−
        33 & 1 & 20\\
+
33 & 1 & 20\\
−
        36 & 1 & 12\\
+
36 & 1 & 12\\
−
        39 & 1 & 24\\
+
39 & 1 & 24\\
−
        42 & 1 & 12\\
+
42 & 1 & 12\\
−
        45 & 1 & 24\\
+
45 & 1 & 24\\
−
        48 & 1 & 16\\
+
48 & 1 & 16\\
−
        51 & 1 & 32\\
+
51 & 1 & 32\\
−
        54 & 1 & 18\\
+
54 & 1 & 18\\
−
        57 & 1 & 36\\
+
57 & 1 & 36\\
−
        60 & 1 & 16\\
+
60 & 1 & 16\\
−
        \bottomrule
+
\hline
−
      \end{tabular}
+
\end{array}
−
  \end{center}
+
</cmath>
−
 
 
 
Adding up the entries in the last column of the table gives the final answer <math>\boxed{220}</math>.
 
Adding up the entries in the last column of the table gives the final answer <math>\boxed{220}</math>.

Latest revision as of 19:05, 10 March 2015

Problem

Paula the Painter initially paints every complex number black. When Paula toggles a complex number, she paints it white if it was previously black, and black if it was previously white. For each $k=1,2,\dots,20$, Paula progressively toggles the roots of $x^{2k}+x^k+1$. Let $N$ be the number of complex numbers are white at the end of this process. Find $N$.

Solution

First, note that $x^{2k}+x^k+1=(x^{3k}-1)/(x^k-1)$. Let $z_1,z_2,\dots,z_n$ be the distinct complex numbers that were toggled, where $n$ is a positive integer, and for each complex number $z$, let $t(z)$ be the number of times $z$ was toggled. Then, we have this relation: \[\prod_{k=1}^{20}(x^{2k}+x^k+1)=\prod_{k=1}^{20}\frac{x^{3k}-1}{x^k-1}=\prod_{i=1}^n (x-z_i)^{t(z_i)}.\tag{1}\]

The problem is equivalent to finding the number of complex numbers $z_i$ such that $t(z_i)$ is odd.

We now focus on the second formula in $(1)$. From this formula, we know that all of the $z_i$ must be roots of unity. Furthermore, for each $z_i$, $t(z_i)$ is the number of factors in the numerator that have $z_i$ as a root minus the number of factors in the denominator that have $z_i$ as a root, since no polynomial of the form $x^n-1$ has a repeated root.

Now let $\zeta_n$ denote a primitive $n$th root of unity. First, when $3\nmid n$, there are an equal number of factors in the numerator of the fraction as in the denominator of the fraction which have $\zeta_n$ as a root, so $t(\zeta_n)=0$ in this case.

We now consider the case when $3\mid n$. The numerator has $\lfloor 60/n\rfloor$ factors with $\zeta_n$ as a root, while the denominator has $\lfloor 20/n\rfloor$ factors with $\zeta_n$ as a root. Therefore, in this case, $t(\zeta_n)=\lfloor 60/n\rfloor-\lfloor 20/n\rfloor$. As there are $\phi(n)$ primitive $n$th roots of unity for each $n$, every $n$ with $t(\zeta_n)$ odd will contribute $\phi(n)$ to the sum. The table below shows the calculations for $n=3,6,9,\dots,60$.

\[\begin{array}{cccc} \hline n & t(\zeta_n)=\lfloor 60/n\rfloor -\lfloor 20/n\rfloor & \text{Contribution}\\ \hline 3 & 14 & 0\\ 6 & 7 & 2\\ 9 & 4 & 0\\ 12 & 4 & 0\\ 15 & 3 & 8\\ 18 & 2 & 0\\ 21 & 2 & 0\\ 24 & 2 & 0\\ 27 & 2 & 0\\ 30 & 2 & 0\\ 33 & 1 & 20\\ 36 & 1 & 12\\ 39 & 1 & 24\\ 42 & 1 & 12\\ 45 & 1 & 24\\ 48 & 1 & 16\\ 51 & 1 & 32\\ 54 & 1 & 18\\ 57 & 1 & 36\\ 60 & 1 & 16\\ \hline \end{array}\] Adding up the entries in the last column of the table gives the final answer $\boxed{220}$.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Mock_AIME_I_2012_Problems/Problem_15&oldid=68711"