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 , Paula progressively toggles the roots of
. Let
be the number of complex numbers are white at the end of this process. Find
.
Solution
First, note that . Let
be the distinct complex numbers that were toggled, where
is a positive integer, and for each complex number
, let
be the number of times
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 such that
is odd.
We now focus on the second formula in \eqref{eq:product}. From this formula, we know that all of the must be roots of unity. Furthermore, for each
,
is the number of factors in the numerator that have
as a root minus the number of factors in the denominator that have
as a root, since no polynomial of the form
has a repeated root.
Now let denote a primitive
th root of unity. First, when
, there are an equal number of factors in the numerator of the fraction as in the denominator of the fraction which have
as a root, so
in this case.
We now consider the case when . The numerator has
factors with
as a root, while the denominator has
factors with
as a root. Therefore, in this case,
. As there are
primitive
th roots of unity for each
, every
with
odd will contribute
to the sum. The table below shows the calculations for
.
\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 .