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

m
m
(16 intermediate revisions by 14 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 Viète's identities. 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>\Re{(\omega)}</math> is some integer over <math>2</math>. <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}}

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