Difference between revisions of "Mock AIME I 2012 Problems/Problem 15"
Mathgeek2006 (talk | contribs) m |
Mathgeek2006 (talk | contribs) m (→Solution) |
||
Line 4: | Line 4: | ||
==Solution== | ==Solution== | ||
First, note that <math>x^{2k}+x^k+1=(x^{3k}-1)/(x^k-1)</math>. Let <math>z_1,z_2,\dots,z_n</math> be the distinct complex numbers that were toggled, where <math>n</math> is a positive integer, and for each complex number <math>z</math>, let <math>t(z)</math> be the number of times <math>z</math> was toggled. Then, we have this relation: | First, note that <math>x^{2k}+x^k+1=(x^{3k}-1)/(x^k-1)</math>. Let <math>z_1,z_2,\dots,z_n</math> be the distinct complex numbers that were toggled, where <math>n</math> is a positive integer, and for each complex number <math>z</math>, let <math>t(z)</math> be the number of times <math>z</math> was toggled. Then, we have this relation: | ||
− | + | <cmath> | |
− | + | \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} | |
− | + | </cmath> | |
The problem is equivalent to finding the number of complex numbers <math>z_i</math> such that <math>t(z_i)</math> is odd. | The problem is equivalent to finding the number of complex numbers <math>z_i</math> such that <math>t(z_i)</math> is odd. | ||
− | + | ||
− | We now focus on the second formula in | + | We now focus on the second formula in <math>(1)</math>. From this formula, we know that all of the <math>z_i</math> must be roots of unity. Furthermore, for each <math>z_i</math>, <math>t(z_i)</math> is the number of factors in the numerator that have <math>z_i</math> as a root minus the number of factors in the denominator that have <math>z_i</math> as a root, since no polynomial of the form <math>x^n-1</math> has a repeated root. |
Now let <math>\zeta_n</math> denote a primitive <math>n</math>th root of unity. First, when <math>3\nmid n</math>, there are an equal number of factors in the numerator of the fraction as in the denominator of the fraction which have <math>\zeta_n</math> as a root, so <math>t(\zeta_n)=0</math> in this case. | Now let <math>\zeta_n</math> denote a primitive <math>n</math>th root of unity. First, when <math>3\nmid n</math>, there are an equal number of factors in the numerator of the fraction as in the denominator of the fraction which have <math>\zeta_n</math> as a root, so <math>t(\zeta_n)=0</math> in this case. |
Latest revision as of 20:05, 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:
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
.