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

m (Solution)
m
(11 intermediate revisions by 10 users not shown)
Line 3: Line 3:
 
Let <math>S</math> be the set of all polynomials of the form <math>z^3 + az^2 + bz + c</math>, where <math>a</math>, <math>b</math>, and <math>c</math> are integers. Find the number of polynomials in <math>S</math> such that each of its roots <math>z</math> satisfies either <math>|z| = 20</math> or <math>|z| = 13</math>.
 
Let <math>S</math> be the set of all polynomials of the form <math>z^3 + az^2 + bz + c</math>, where <math>a</math>, <math>b</math>, and <math>c</math> are integers. Find the number of polynomials in <math>S</math> such that each of its roots <math>z</math> satisfies either <math>|z| = 20</math> or <math>|z| = 13</math>.
  
==Solution==
+
==Solution 1==
 +
 
 +
Every cubic with 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:  <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> 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>p+q+r+s=3</math> because there are three roots. We wish to find the number of ways to choose nonnegative integers <math>p,q,r,s</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.
 +
 
 +
==Solution 2 (Systematics)==
 +
This combinatorics problem involves counting, and casework is most appropriate.
 +
There are two cases: either all three roots are real, or one is real and there are two imaginary roots.
 +
 
 +
Case 1: Three roots are of the set <math>{13, -13, 20, -20}</math>. By stars and bars, there is <math>\binom{6}{3}=20</math> ways (3 bars between all four possibilities, and then 3 stars that represent the roots themselves).
 +
 
 +
Case 2: One real root: one of <math>13, -13, 20, -20</math>. Then two imaginary roots left; it is well known that because coefficients of the polynomial are integral (and thus not imaginary), these roots are conjugates. Therefore, either both roots have a norm (also called magnitude) of <math>20</math> or <math>13</math>. Call the root <math>a+bi</math>, where <math>a</math> is not the magnitude of the root; otherwise, it would be case 1. We need integral coefficients: expansion of <math>(x-(a+bi))(x-(a-bi))=-2ax+x^2+(a^2+b^2)</math> tells us that we just need <math>2a</math> to be integral, because <math>a^2+b^2</math> IS the norm of the root! (Note that it is not necessary to multiply by the real root. That won't affect whether or not a coefficient is imaginary.)
 +
Therefore, when the norm is <math>20</math>, the <math>a</math> term can range from <math>-19.5, -19, ...., 0, 0.5, ..., 19.5</math> or <math>79</math> solutions. When the norm is <math>13</math>, the <math>a</math> term has <math>51</math> possibilities from <math>-12.5, -12, ..., 12.5</math>. In total that's 130 total ways to choose the imaginary root. Now, multiply by the ways to choose the real root, <math>4</math>, and you get <math>520</math> for this case.
 +
 
 +
And <math>520+20=540</math> and we are done.
 +
 
 +
==Solution 3 (Comments)==
 +
If the polynomial has one real root and two complex roots, then it can be factored as <math>(z-r)(z^2+pz+q), </math> where <math>r</math> is real with <math>|r|=13,20</math> and <math>p,q</math> are integers with <math>p^2 <4q.</math> The roots <math>z_1</math> and <math>z_2</math> are conjugates. We have <math>|z_1|^2=|z_2|^2=z_1z_2=q.</math> So <math>q</math> is either <math>20^2</math> or <math>13^2</math>. The only requirement for <math>p</math> is <math>p<\sqrt{4q^2}=2\sqrt{q}.</math> All such quadratic equations are listed as follows:
 +
 
 +
<math>z^2+pz+20^2,</math> where <math>p=0,\pm1,\pm2,\cdots,\pm 39,</math>
 +
 
 +
<math>z^2+pz+13^2,</math> where <math>p=0,\pm1,\pm2,\cdots,\pm 25</math>.
 +
 
 +
Total of 130 equations, multiplied by 4 (the number of cases for real <math>r</math>, we have 520 equations, as indicated in the solution.
 +
 
 +
-JZ
 +
 
 +
==Solution 4==
 +
There are two cases: either all the roots are real, or one is real and two are imaginary.
 +
 
 +
<b>Case 1:</b> All roots are real.
 +
Then each of the roots is a member of the set <math>\{-20, 20, -13, 13\}</math>. It splits into three sub-cases: either no two are the same, exactly two are the same, or all three are the same.
 +
 
 +
<b>Sub-case 1.1:</b> No two are the same.
 +
This is obviously <math>\dbinom{4}{3}=4</math>.
 +
 
 +
<b>Sub-case 1.2:</b> Exactly two are the same.
 +
There are four ways to choose the root that will repeat twice, and three ways to choose the remaining root. For this sub-case, <math>4\cdot 3=12</math>.
 +
 
 +
<b>Sub-case 1.3:</b> All three are the same.
 +
This is obviously <math>4</math>.
 +
 
 +
Thus for case one, we have <math>4+12+4=20</math> polynomials in <math>S</math>. We now have case two, which we state below.
 +
 
 +
<b>Case 2:</b> Two roots are imaginary and one is real.
 +
Let these roots be <math>p-qi</math>, <math>p+qi</math>, and <math>r</math>. Then by Vieta's formulas
 +
* <math>-(2p+r)=a</math>;
 +
* <math>p^{2}+q^{2}+2pr=b</math>;
 +
* <math>-\left(p^{2}+q^{2}\right)r=c</math>.
 +
Since <math>a</math>, <math>b</math>, <math>c</math>, and <math>r</math> are integers, we have that <math>p=\frac{1}{2}k</math> for some integer <math>k</math>. Case two splits into two sub-cases now:
 +
 
 +
<b>Sub-case 2.1:</b> <math>|p-qi|=|p+qi|=13</math>.
 +
Obviously, <math>|p|<13</math>. The <math>51</math> cases in which <math>p</math> is either <math>0,\pm\frac{1}{2},\pm\frac{2}{2},\pm\frac{3}{2},\ldots,\pm\frac{25}{2}</math> are acceptable. Each can pair with one value of <math>q</math> and four values of <math>r</math>, adding <math>51\cdot 4=204</math> polynomials to <math>S</math>.
 +
 
 +
<b>Sub-case 2.2:</b> <math>|p-qi|=|p+qi|=20</math>.
 +
Obviously, <math>|p|<20</math>. Here, the <math>79</math> cases in which <math>p</math> is either <math>0,\pm\frac{1}{2},\pm\frac{2}{2},\pm\frac{3}{2},\ldots,\pm\frac{39}{2}</math> are acceptable. Again, each can pair with a single value of <math>q</math> as well as four values of <math>r</math>, adding <math>79\cdot 4=316</math> polynomials to <math>S</math>.
 +
 
 +
Thus for case two, <math>204+316=520</math> polynomials are part of <math>S</math>.
 +
 
 +
All in all, <math>20+204+316=\boxed{540}</math> polynomials can call <math>S</math> home.
 +
 
 +
 
 +
==Video Solution==
 +
https://youtu.be/-U65hhr1Smw?si=2JfRYL032MhUe276
 +
 
 +
~MathProblemSolvingSkills.com
  
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.
 
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>.
 
  
 
==See Also==
 
==See Also==
 
{{AIME box|year=2013|n=II|num-b=11|num-a=13}}
 
{{AIME box|year=2013|n=II|num-b=11|num-a=13}}
 
{{MAA Notice}}
 
{{MAA Notice}}

Revision as of 16:41, 20 June 2024

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 1

Every cubic with 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$ 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 $p+q+r+s=3$ because there are three roots. We wish to find the number of ways to choose nonnegative integers $p,q,r,s$ 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.

Solution 2 (Systematics)

This combinatorics problem involves counting, and casework is most appropriate. There are two cases: either all three roots are real, or one is real and there are two imaginary roots.

Case 1: Three roots are of the set ${13, -13, 20, -20}$. By stars and bars, there is $\binom{6}{3}=20$ ways (3 bars between all four possibilities, and then 3 stars that represent the roots themselves).

Case 2: One real root: one of $13, -13, 20, -20$. Then two imaginary roots left; it is well known that because coefficients of the polynomial are integral (and thus not imaginary), these roots are conjugates. Therefore, either both roots have a norm (also called magnitude) of $20$ or $13$. Call the root $a+bi$, where $a$ is not the magnitude of the root; otherwise, it would be case 1. We need integral coefficients: expansion of $(x-(a+bi))(x-(a-bi))=-2ax+x^2+(a^2+b^2)$ tells us that we just need $2a$ to be integral, because $a^2+b^2$ IS the norm of the root! (Note that it is not necessary to multiply by the real root. That won't affect whether or not a coefficient is imaginary.) Therefore, when the norm is $20$, the $a$ term can range from $-19.5, -19, ...., 0, 0.5, ..., 19.5$ or $79$ solutions. When the norm is $13$, the $a$ term has $51$ possibilities from $-12.5, -12, ..., 12.5$. In total that's 130 total ways to choose the imaginary root. Now, multiply by the ways to choose the real root, $4$, and you get $520$ for this case.

And $520+20=540$ and we are done.

Solution 3 (Comments)

If the polynomial has one real root and two complex roots, then it can be factored as $(z-r)(z^2+pz+q),$ where $r$ is real with $|r|=13,20$ and $p,q$ are integers with $p^2 <4q.$ The roots $z_1$ and $z_2$ are conjugates. We have $|z_1|^2=|z_2|^2=z_1z_2=q.$ So $q$ is either $20^2$ or $13^2$. The only requirement for $p$ is $p<\sqrt{4q^2}=2\sqrt{q}.$ All such quadratic equations are listed as follows:

$z^2+pz+20^2,$ where $p=0,\pm1,\pm2,\cdots,\pm 39,$

$z^2+pz+13^2,$ where $p=0,\pm1,\pm2,\cdots,\pm 25$.

Total of 130 equations, multiplied by 4 (the number of cases for real $r$, we have 520 equations, as indicated in the solution.

-JZ

Solution 4

There are two cases: either all the roots are real, or one is real and two are imaginary.

Case 1: All roots are real. Then each of the roots is a member of the set $\{-20, 20, -13, 13\}$. It splits into three sub-cases: either no two are the same, exactly two are the same, or all three are the same.

Sub-case 1.1: No two are the same. This is obviously $\dbinom{4}{3}=4$.

Sub-case 1.2: Exactly two are the same. There are four ways to choose the root that will repeat twice, and three ways to choose the remaining root. For this sub-case, $4\cdot 3=12$.

Sub-case 1.3: All three are the same. This is obviously $4$.

Thus for case one, we have $4+12+4=20$ polynomials in $S$. We now have case two, which we state below.

Case 2: Two roots are imaginary and one is real. Let these roots be $p-qi$, $p+qi$, and $r$. Then by Vieta's formulas

  • $-(2p+r)=a$;
  • $p^{2}+q^{2}+2pr=b$;
  • $-\left(p^{2}+q^{2}\right)r=c$.

Since $a$, $b$, $c$, and $r$ are integers, we have that $p=\frac{1}{2}k$ for some integer $k$. Case two splits into two sub-cases now:

Sub-case 2.1: $|p-qi|=|p+qi|=13$. Obviously, $|p|<13$. The $51$ cases in which $p$ is either $0,\pm\frac{1}{2},\pm\frac{2}{2},\pm\frac{3}{2},\ldots,\pm\frac{25}{2}$ are acceptable. Each can pair with one value of $q$ and four values of $r$, adding $51\cdot 4=204$ polynomials to $S$.

Sub-case 2.2: $|p-qi|=|p+qi|=20$. Obviously, $|p|<20$. Here, the $79$ cases in which $p$ is either $0,\pm\frac{1}{2},\pm\frac{2}{2},\pm\frac{3}{2},\ldots,\pm\frac{39}{2}$ are acceptable. Again, each can pair with a single value of $q$ as well as four values of $r$, adding $79\cdot 4=316$ polynomials to $S$.

Thus for case two, $204+316=520$ polynomials are part of $S$.

All in all, $20+204+316=\boxed{540}$ polynomials can call $S$ home.


Video Solution

https://youtu.be/-U65hhr1Smw?si=2JfRYL032MhUe276

~MathProblemSolvingSkills.com


See Also

2013 AIME II (ProblemsAnswer KeyResources)
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

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png