Difference between revisions of "2012 AMC 12B Problems/Problem 23"
Line 5: | Line 5: | ||
<math>\textbf{(A)}\ 84\qquad\textbf{(B)}\ 92\qquad\textbf{(C)}\ 100\qquad\textbf{(D)}\ 108\qquad\textbf{(E)}\ 120 </math> | <math>\textbf{(A)}\ 84\qquad\textbf{(B)}\ 92\qquad\textbf{(C)}\ 100\qquad\textbf{(D)}\ 108\qquad\textbf{(E)}\ 120 </math> | ||
− | |||
− | |||
− | |||
==Solution (doubtful) == | ==Solution (doubtful) == | ||
− | Since < | + | Since <math>z_0</math> is a root of <math>P</math>, and <math>P</math> has integer coefficients, <math>z_0</math> must be algebraic. Since <math>z_0</math> is algebraic and lies on the unit circle, <math>z_0</math> must be a root of unity (Comment: this is not true. See this link: [http://math.stackexchange.com/questions/4323/are-all-algebraic-integers-with-absolute-value-1-roots-of-unity]). Since <math>P</math> has degree 4, it seems reasonable (and we will assume this only temporarily) that <math>z_0</math> must be a 2nd, 3rd, or 4th root of unity. These are among the set <math>\{\pm1,\pm i,(-1\pm i\sqrt{3})/2\}</math>. Since complex roots of polynomials come in conjugate pairs, we have that <math>P</math> has one (or more) of the following factors: <math>z+1</math>, <math>z-1</math>, <math>z^2+1</math>, or <math>z^2+z+1</math>. If <math>z=1</math> then <math>a+b+c+d+4=0</math>; a contradiction since <math>a,b,c,d</math> are non-negative. On the other hand, suppose <math>z=-1</math>. Then <math>(a+c)-(b+d)=4</math>. This implies <math>a+b=8,7,6,5,4</math> while <math>b+d=4,3,2,1,0</math> correspondingly. After listing cases, the only such valid <math>a,b,c,d</math> are <math>4,4,4,0</math>, <math>4,3,3,0</math>, <math>4,2,2,0</math>, <math>4,1,1,0</math>, and <math>4,0,0,0</math>. |
− | Now suppose < | + | Now suppose <math>z=i</math>. Then <math>4=(a-c)i+(b-d)</math> whereupon <math>a=c</math> and <math>b-d=4</math>. But then <math>a=b=c</math> and <math>d=a-4</math>. This gives only the cases <math>a,b,c,d</math> equals <math>4,4,4,0</math>, which we have already counted in a previous case. |
− | Suppose < | + | Suppose <math>z=-i</math>. Then <math>4=i(c-a)+(b-d)</math> so that <math>a=c</math> and <math>b=4+d</math>. This only gives rise to <math>a,b,c,d</math> equal <math>4,4,4,0</math> which we have previously counted. |
− | Finally suppose < | + | Finally suppose <math>z^2+z+1</math> divides <math>P</math>. Using polynomial division ((or that <math>z^3=1</math> to make the same deductions) we ultimately obtain that <math>b=4+c</math>. This can only happen if <math>a,b,c,d</math> is <math>4,4,0,0</math>. |
Hence we've the polynomials | Hence we've the polynomials | ||
Line 27: | Line 24: | ||
<cmath>4x^4+4x^3</cmath> | <cmath>4x^4+4x^3</cmath> | ||
<cmath>4x^4+4x^3+4x^2</cmath> | <cmath>4x^4+4x^3+4x^2</cmath> | ||
− | However, by inspection < | + | However, by inspection <math>4x^4+4x^3+4x^2+4x+4</math> has roots on the unit circle, because <math>x^4+x^3+x^2+x+1=(x^5-1)/(x-1)</math> which brings the sum to 92 (choice B). Note that this polynomial has a 5th root of unity as a root. We will show that we were \textit{almost} correct in our initial assumption; that is that <math>z_0</math> is at most a 5th root of unity, and that the last polynomial we obtained is the last polynomial with the given properties. Suppose that <math>z_0</math> in an <math>n</math>th root of unity where <math>n>5</math>, and <math>z_0</math> is not a 3rd or 4th root of unity. (Note that 1st and 2nd roots of unity are themselves 4th roots of unity). If <math>n</math> is prime, then \textit{every} <math>n</math>th root of unity except 1 must satisfy our polynomial, but since <math>n>5</math> and the degree of our polynomial is 4, this is impossible. Suppose <math>n</math> is composite. If it has a prime factor <math>p</math> greater than 5 then again every <math>p</math>th root of unity must satisfy our polynomial and we arrive at the same contradiction. Therefore suppose <math>n</math> is divisible only by 2,3,or 5. Since by hypothesis <math>z_0</math> is not a 2nd or 3rd root of unity, <math>z_0</math> must be a 5th root of unity. Since 5 is prime, every 5th root of unity except 1 must satisfy our polynomial. That is, the other 4 complex 5th roots of unity must satisfy <math>P(z_0)=0</math>. But <math>(x^5-1)/(x-1)</math> has exactly all 5th roots of unity excluding 1, and <math>(x^5-1)/(x-1)=x^4+x^3+x^2+x+1</math>. Thus this must divide <math>P</math> which implies <math>P(x)=4(x^4+x^3+x^2+x+1)</math>. This completes the proof. |
+ | |||
+ | |||
+ | == Solution == | ||
+ | First, assume that <math>z_0\in \mathbb{R}</math>, so <math>z_0=1</math> or <math>-1</math>. <math>1</math> does not work because <math>P(1)\geq 4</math>. Assume that <math>z_0=-1</math>. Then <math>0=P(-1)=4-a+b-c+d</math>, we have <math>4+b+d=a+c\leq 4+b</math>, so <math>d=0</math>. Also, <math>a=4</math> has to be true since <math>4+b=a+c \leq a+b</math>. Now <math>4+b=4+c</math> deduces <math>b=c</math>, therefore the only possible choices for <math>(a,b,c,d)</math> are <math>(4,t,t,0)</math>. In these cases, <math>P(-1)=4-4+t-t+0=0</math>. The sum of <math>P(1)</math> over these cases is <math>\sum_{t=0}^{4} (4+4+t+t) = 40+20=60</math>. | ||
+ | |||
+ | Second, assume that <math>z_0\in \mathbb{C} \backslash \mathbb{R}</math>, so <math>z_0=x_0+iy_0</math> for some real <math>x_0, y_0</math>, <math>|x_0|<1</math>. By conjugate roots theorem we have that <math>P(z_0)=P(z_0^{*})=0</math>, therefore <math>(z-z_0)(z-z_0^{*}) = (z^2 - 2x_0 + 1)</math> is a factor of <math>P(z)</math>, and we may assume that | ||
+ | |||
+ | <cmath>P(z) = (z^2-2x_0 z + 1)(4z^2 + pz + d)</cmath> | ||
+ | |||
+ | for some real <math>p</math>. Expanding this polynomial and comparing the coefficients, we have the following equations: | ||
+ | |||
+ | <cmath>p-8x_0 = a</cmath> | ||
+ | <cmath>d+4-2px_0 = b</cmath> | ||
+ | <cmath>p-2dx_0 = c</cmath> | ||
+ | |||
+ | From the first and the third we may deduce that <math>2x_0 = \frac{a-c}{d-4}</math> and that <math>p=\frac{da-4c}{d-4}</math>, if <math>d\neq 4</math> (we will consider <math>d=4</math> by the end). Let <math>k=2px_0=\frac{(a-c)(da-4c)}{(4-d)^2}</math>. From the second equation, we know that <math>k=d+4-b</math> is a non-negative integer. Consider the following cases: | ||
+ | |||
+ | Case 1: <math>a=c</math>. Then <math>k=0</math>, <math>b=d+4</math>, so <math>a=b=c=4</math>, <math>d=0</math>. <math>x_0=0</math>. In this case, <math>P(z)</math> has a root <math>z_0=i</math>. However, this case is already covered before (<math>t=4</math>). | ||
+ | Case 2: <math>a>c\geq 0</math>. Then since <math>k\geq 0</math>, we have <math>da-4c\geq 0</math>. However, <math>da \leq 4c</math>, therefore <math>da-4c=0</math>. This is true only when <math>d=c</math>. Also, we get <math>k=0</math> again. In this case, <math>b=d+4</math>, so <math>a=b=4</math>, <math>c=d=0</math>, <math>x_0=-1/2</math>. <math>P(z)</math> has a root <math>z_0=e^{i2\pi/3}</math>. <math>P(1)=12</math>. | ||
+ | Last case: <math>d=4</math>. We have <math>a=b=c=d=4</math> and that <math>P(z)</math> has a root <math>z_0=e^{i2\pi/5}</math>. <math>P(1)=20</math>. | ||
+ | |||
+ | Therefore the desired sum is <math>60+12+20=92 ...\framebox{B}</math>. | ||
+ | |||
+ | |||
+ | The case of <math>d=4</math>. We get <math>a=b=c=d=4</math>. In this case, <math>z_0=e^{i2\pi/5}</math> satisfies the conditions. |
Revision as of 04:03, 6 December 2012
Problem 23
Consider all polynomials of a complex variable, , where
and
are integers,
, and the polynomial has a zero
with
What is the sum of all values
over all the polynomials with these properties?
Solution (doubtful)
Since is a root of
, and
has integer coefficients,
must be algebraic. Since
is algebraic and lies on the unit circle,
must be a root of unity (Comment: this is not true. See this link: [1]). Since
has degree 4, it seems reasonable (and we will assume this only temporarily) that
must be a 2nd, 3rd, or 4th root of unity. These are among the set
. Since complex roots of polynomials come in conjugate pairs, we have that
has one (or more) of the following factors:
,
,
, or
. If
then
; a contradiction since
are non-negative. On the other hand, suppose
. Then
. This implies
while
correspondingly. After listing cases, the only such valid
are
,
,
,
, and
.
Now suppose . Then
whereupon
and
. But then
and
. This gives only the cases
equals
, which we have already counted in a previous case.
Suppose . Then
so that
and
. This only gives rise to
equal
which we have previously counted.
Finally suppose divides
. Using polynomial division ((or that
to make the same deductions) we ultimately obtain that
. This can only happen if
is
.
Hence we've the polynomials
However, by inspection
has roots on the unit circle, because
which brings the sum to 92 (choice B). Note that this polynomial has a 5th root of unity as a root. We will show that we were \textit{almost} correct in our initial assumption; that is that
is at most a 5th root of unity, and that the last polynomial we obtained is the last polynomial with the given properties. Suppose that
in an
th root of unity where
, and
is not a 3rd or 4th root of unity. (Note that 1st and 2nd roots of unity are themselves 4th roots of unity). If
is prime, then \textit{every}
th root of unity except 1 must satisfy our polynomial, but since
and the degree of our polynomial is 4, this is impossible. Suppose
is composite. If it has a prime factor
greater than 5 then again every
th root of unity must satisfy our polynomial and we arrive at the same contradiction. Therefore suppose
is divisible only by 2,3,or 5. Since by hypothesis
is not a 2nd or 3rd root of unity,
must be a 5th root of unity. Since 5 is prime, every 5th root of unity except 1 must satisfy our polynomial. That is, the other 4 complex 5th roots of unity must satisfy
. But
has exactly all 5th roots of unity excluding 1, and
. Thus this must divide
which implies
. This completes the proof.
Solution
First, assume that , so
or
.
does not work because
. Assume that
. Then
, we have
, so
. Also,
has to be true since
. Now
deduces
, therefore the only possible choices for
are
. In these cases,
. The sum of
over these cases is
.
Second, assume that , so
for some real
,
. By conjugate roots theorem we have that
, therefore
is a factor of
, and we may assume that
for some real . Expanding this polynomial and comparing the coefficients, we have the following equations:
From the first and the third we may deduce that and that
, if
(we will consider
by the end). Let
. From the second equation, we know that
is a non-negative integer. Consider the following cases:
Case 1: . Then
,
, so
,
.
. In this case,
has a root
. However, this case is already covered before (
).
Case 2:
. Then since
, we have
. However,
, therefore
. This is true only when
. Also, we get
again. In this case,
, so
,
,
.
has a root
.
.
Last case:
. We have
and that
has a root
.
.
Therefore the desired sum is .
The case of . We get
. In this case,
satisfies the conditions.