# Difference between revisions of "Mock AIME I 2012 Problems/Problem 15"

(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) m |
||

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>. | ||

− | + | <cmath> | |

− | + | \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} | |

− | + | </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 20: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 , 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 .

Adding up the entries in the last column of the table gives the final answer .