Difference between revisions of "2013 AIME II Problems/Problem 12"

Revision as of 00:29, 18 January 2016

Problem 12

Let $S$ be the set of all polynomials of the form $z^3 + az^2 + bz + c$ , where $a$ , $b$ , and $c$ are integers. Find the number of polynomials in $S$ such that each of its roots $z$ satisfies either $|z| = 20$ or $|z| = 13$ .

Solution

Every cubic in real coefficients has to have either three real roots or one real and two nonreal roots which are conjugates. This follows from Vieta's formulas.

Case 1: $f(z)=(z-r)(z-\omega)(z-\omega^*)$ , where $r\in \mathbb{R}$ , $\omega$ is nonreal, and $\omega^*$ is the complex conjugate of omega (note that we may assume that $\Im(\omega)>0$ ).

The real root $r$ must be one of $-20$ , $20$ , $-13$ , or $13$ . By Viète's formulas, $a=-(r+\omega+\omega^*)$ , $b=|\omega|^2+r(\omega+\omega^*)$ , and $c=-r|\omega|^2$ . But $\omega+\omega^*=2\Re{(\omega)}$ (i.e., adding the conjugates cancels the imaginary part). Therefore, to make $a$ is an integer, $2\Re{(\omega)}$ must be an integer. Conversely, if $\omega+\omega^*=2\Re{(\omega)}$ is an integer, then $a,b,$ and $c$ are clearly integers. Therefore $2\Re{(\omega)}\in \mathbb{Z}$ is equivalent to the desired property. Let $\omega=\alpha+i\beta$ .

Subcase 1.1: $|\omega|=20$ .

In this case, $\omega$ lies on a circle of radius $20$ in the complex plane. As $\omega$ is nonreal, we see that $\beta\ne 0$ . Hence $-20<\Re{(\omega)}< 20$ , or rather $-40<2\Re{(\omega)}< 40$ . We count $79$ integers in this interval, each of which corresponds to a unique complex number on the circle of radius $20$ with positive imaginary part.

Subcase 1.2: $|\omega|=13$ .

In this case, $\omega$ lies on a circle of radius $13$ in the complex plane. As $\omega$ is nonreal, we see that $\beta\ne 0$ . Hence $-13<\Re{(\omega)}< 13$ , or rather $-26<2\Re{(\omega)}< 26$ . We count $51$ integers in this interval, each of which corresponds to a unique complex number on the circle of radius $13$ with positive imaginary part.

Therefore, there are $79+51=130$ choices for $\omega$ . We also have $4$ choices for $r$ , hence there are $4\cdot 130=520$ total polynomials in this case.

Case 2: $f(z)=(z-r_1)(z-r_2)(z-r_3)$ , where $r_1,r_2,r_3$ are all real.

In this case, there are four possible real roots, namely $\pm 13, \pm20$ . Let $p$ be the number of times that $13$ appears among $r_1,r_2,r_3$ , and define $q,r,s$ similarly for $-13,20$ , and $-20$ , respectively. Then $a+b+c+d=3$ because there are three roots. We wish to find the number of ways to choose nonnegative integers $a,b,c,d$ that satisfy that equation. By balls and urns, these can be chosen in $\binom{6}{3}=20$ ways.

Therefore, there are a total of $520+20=\boxed{540}$ polynomials with the desired property.

@@ Line 5: / Line 5: @@
 ==Solution==
-Every cubic in real coefficients has to have either three real roots or one real and two complex roots which are conjugates. This follows from [[Vieta's formulas]]. Factorise the polynomial <math>(z-r)(z-\omega)(z-\omega^*)</math>, where <math>\omega^*</math> is the complex conjugate of omega. We know that <math>r</math> is the real root which must be <math>-20</math>, <math>20</math>, <math>-13</math>, or <math>13</math>, and it doesn't matter which. <math>|\omega|=|\omega^*|=20 \ \text{or}\ 13</math>. Let <math>\omega=\alpha+i\beta</math>. Viète tells us that <math>a=-(r+\omega+\omega^*</math>), but <math>\omega+\omega^*=2\Re{(\omega)}</math> (i.e., adding the conjugates cancels the imaginary part). a the quadratic coefficient must be an integer so <math>2\Re{(\omega)}</math> is some integer. <math>|\omega|=|\omega^*|=</math>20 or 13 so you have a bound on <math>\Re{(\omega)}</math>: either <math>-13\leq\Re{(\omega)}\leq 13</math> or <math>-20\leq\Re{(\omega)}\leq 20</math>. Don't forget zero! We're not double counting the numbers between <math>-13</math> and <math>13</math> here because there's an imaginary part too -- <math>\sqrt{\alpha^2+\beta^2}=|\omega|</math>, and what you get when you solve for beta will depend on what the magnitude was.
+Every cubic in real coefficients has to have either three real roots or one real and two nonreal roots which are conjugates. This follows from [[Vieta's formulas]].
-You have the magnitude so <math>\Re{(\omega)}</math> determines <math>\omega</math> totally (you can solve for the imaginary part) and <math>\omega</math> determines <math>\omega^*</math>.
-Now just count: 4 possibilities for the real root times [(52+1) possibilities if <math>|\omega|=13</math> plus (80+1) possibilities if <math>|\omega|=20</math> = 536. But this is not all, we also have <math>{4\choose{3}}=4</math> ways of constructing a totally real polynomial (all real roots), which gives you <math>\boxed{540}</math>.
+*Case 1:  <math>f(z)=(z-r)(z-\omega)(z-\omega^*)</math>, where <math>r\in \mathbb{R}</math>,  <math>\omega</math> is nonreal, and <math>\omega^*</math> is the complex conjugate of omega (note that we may assume that <math>\Im(\omega)>0</math>).
+The real root <math>r</math> must be one of <math>-20</math>, <math>20</math>, <math>-13</math>, or <math>13</math>. By Viète's formulas, <math>a=-(r+\omega+\omega^*)</math>, <math>b=|\omega|^2+r(\omega+\omega^*)</math>, and <math>c=-r|\omega|^2</math>. But <math>\omega+\omega^*=2\Re{(\omega)}</math> (i.e., adding the conjugates cancels the imaginary part). Therefore, to make <math>a</math> is an integer, <math>2\Re{(\omega)}</math> must be an integer. Conversely, if <math>\omega+\omega^*=2\Re{(\omega)}</math> is an integer, then <math>a,b,</math> and <math>c</math> are clearly integers. Therefore <math>2\Re{(\omega)}\in \mathbb{Z}</math> is equivalent to the desired property. Let <math>\omega=\alpha+i\beta</math>.
+*Subcase 1.1: <math>|\omega|=20</math>.
+In this case, <math>\omega</math> lies on a circle of radius <math>20</math> in the complex plane. As <math>\omega</math> is nonreal, we see that <math>\beta\ne 0</math>.  Hence <math>-20<\Re{(\omega)}< 20</math>, or rather <math>-40<2\Re{(\omega)}< 40</math>. We count <math>79</math> integers in this interval, each of which corresponds to a unique complex number on the circle of radius <math>20</math> with positive imaginary part.
+*Subcase 1.2: <math>|\omega|=13</math>.
+In this case, <math>\omega</math> lies on a circle of radius <math>13</math> in the complex plane. As <math>\omega</math> is nonreal, we see that <math>\beta\ne 0</math>.  Hence <math>-13<\Re{(\omega)}< 13</math>, or rather <math>-26<2\Re{(\omega)}< 26</math>. We count <math>51</math> integers in this interval, each of which corresponds to a unique complex number on the circle of radius <math>13</math> with positive imaginary part.
+Therefore, there are <math>79+51=130</math> choices for <math>\omega</math>. We also have <math>4</math> choices for <math>r</math>, hence there are <math>4\cdot 130=520</math> total polynomials in this case.
+*Case 2: <math>f(z)=(z-r_1)(z-r_2)(z-r_3)</math>, where <math>r_1,r_2,r_3</math> are all real.
+In this case, there are four possible real roots, namely <math>\pm 13, \pm20</math>. Let <math>p</math> be the number of times that <math>13</math> appears among <math>r_1,r_2,r_3</math>, and define <math>q,r,s</math> similarly for <math>-13,20</math>, and <math>-20</math>, respectively. Then <math>a+b+c+d=3</math> because there are three roots. We wish to find the number of ways to choose nonnegative integers <math>a,b,c,d</math> that satisfy that equation. By balls and urns, these can be chosen in <math>\binom{6}{3}=20</math> ways.
+Therefore, there are a total of <math>520+20=\boxed{540}</math> polynomials with the desired property.
 ==See Also==
 {{AIME box|year=2013|n=II|num-b=11|num-a=13}}
 {{MAA Notice}}

2013 AIME II (Problems • Answer Key • Resources)
Preceded by Problem 11	Followed by Problem 13
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

Page

Toolbox

Search

Difference between revisions of "2013 AIME II Problems/Problem 12"

Revision as of 00:29, 18 January 2016

Problem 12

Solution

See Also