Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

m (→‎Solution)
m (see also box)
 
Line 45: Line 45:
 
</cmath>
 
</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>.
 +
 +
==See Also==
 +
*<math>\textbf{Last Problem}</math>
 +
*[[Mock AIME I 2012 Problems/Problem 14| Previous Problem]]
 +
*[[Mock AIME I 2012 Problems]]

Latest revision as of 10:02, 11 March 2025

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

See Also

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Mock_AIME_I_2012_Problems/Problem_15&oldid=244744"