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: $\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}$ .

Page

Toolbox

Search

Mock AIME I 2012 Problems/Problem 15

Problem

Solution