Mock AIME I 2012 Problems/Problem 15
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 .
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:
The problem is equivalent to finding the number of complex numbers such that is odd.
We now focus on the second formula in . 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 .
Adding up the entries in the last column of the table gives the final answer .