Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

m (→‎Solution: Fixed inconsistency in definition of variables for balls and urns (i.e. "p,q,r,s" "a,b,c,d"))
m (Added solution)
Line 24: Line 24:
 
Therefore, there are a total of <math>520+20=\boxed{540}</math> polynomials with the desired property.
 
Therefore, there are a total of <math>520+20=\boxed{540}</math> polynomials with the desired property.
  
 +
==Solution 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.
 
==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 19:37, 2 March 2018

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 $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 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.

See Also

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

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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2013_AIME_II_Problems/Problem_12&oldid=92637"