Mock AIME I 2012 Problems/Problem 15

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{center}
     \begin{tabular}{cccc}
        \toprule
         &  & Contribution\\
        \midrule
        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\\
        \bottomrule
     \end{tabular}
  \end{center}

Adding up the entries in the last column of the table gives the final answer $\boxed{220}$ .

Page

Toolbox

Search

Mock AIME I 2012 Problems/Problem 15

Problem

Solution