Art of Problem Solving
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

Mock AIME I 2012 Problems/Problem 15: Difference between revisions

Newer edit →
Esque (talk | contribs)
30 edits
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..."
 
Mathgeek2006 (talk | contribs)
editor
430 edits
mNo edit summary
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>.

Revision as of 19:04, 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: 

  \begin{equation}\label{eq:product}
     \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)}.
  \end{equation}

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 \eqref{eq:product}. 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://wiki.aopstest.com/wiki/index.php?title=Mock_AIME_I_2012_Problems/Problem_15&oldid=68710"