Difference between revisions of "2013 AMC 12B Problems/Problem 25"
Armalite46 (talk | contribs) m (→Solution) |
Isabelchen (talk | contribs) (→Solution 3) |
||
(6 intermediate revisions by 4 users not shown) | |||
Line 5: | Line 5: | ||
where <math> c_1,c_2,\cdots, c_{n-1} </math> are integers and <math>P(z)</math> has distinct roots of the form <math>a+ib</math> with <math>a</math> and <math>b</math> integers. How many polynomials are in <math>G</math>? | where <math> c_1,c_2,\cdots, c_{n-1} </math> are integers and <math>P(z)</math> has distinct roots of the form <math>a+ib</math> with <math>a</math> and <math>b</math> integers. How many polynomials are in <math>G</math>? | ||
− | <math> \textbf{(A)}\ 288\qquad\textbf{(B)}\ 528\qquad\textbf{(C)}\ 576\qquad\textbf{(D | + | <math> \textbf{(A)}\ 288\qquad\textbf{(B)}\ 528\qquad\textbf{(C)}\ 576\qquad\textbf{(D)}\ 992\qquad\textbf{(E)}\ 1056 </math> |
− | ==Solution== | + | |
+ | ==Solution 1== | ||
If we factor into irreducible polynomials (in <math>\mathbb{Q}[x]</math>), each factor <math>f_i</math> has exponent <math>1</math> in the factorization and degree at most <math>2</math> (since the <math>a+bi</math> with <math>b\ne0</math> come in conjugate pairs with product <math>a^2+b^2</math>). Clearly we want the product of constant terms of these polynomials to equal <math>50</math>; for <math>d\mid 50</math>, let <math>f(d)</math> be the number of permitted <math>f_i</math> with constant term <math>d</math>. It's easy to compute <math>f(1)=2</math>, <math>f(2)=3</math>, <math>f(5)=5</math>, <math>f(10)=5</math>, <math>f(25)=6</math>, <math>f(50)=7</math>, and obviously <math>f(d) = 1</math> for negative <math>d\mid 50</math>. | If we factor into irreducible polynomials (in <math>\mathbb{Q}[x]</math>), each factor <math>f_i</math> has exponent <math>1</math> in the factorization and degree at most <math>2</math> (since the <math>a+bi</math> with <math>b\ne0</math> come in conjugate pairs with product <math>a^2+b^2</math>). Clearly we want the product of constant terms of these polynomials to equal <math>50</math>; for <math>d\mid 50</math>, let <math>f(d)</math> be the number of permitted <math>f_i</math> with constant term <math>d</math>. It's easy to compute <math>f(1)=2</math>, <math>f(2)=3</math>, <math>f(5)=5</math>, <math>f(10)=5</math>, <math>f(25)=6</math>, <math>f(50)=7</math>, and obviously <math>f(d) = 1</math> for negative <math>d\mid 50</math>. | ||
Line 13: | Line 14: | ||
We do casework on the (unique) even constant term <math>d\in\{\pm2,\pm10,\pm50\}</math> in our product. For convenience, let <math>F(d)</math> be the number of ways to get a product of <math>50/d</math> without using <math>\pm 1</math> (so only using <math>\pm5,\pm25</math>) and recall <math>f(-1) = 1</math>; then our final answer will be <math>2^{f(1)}\sum_{d\in\{2,10,50\}}(f(-d)+f(d))(F(-d)+F(d))</math>. It's easy to compute <math>F(-50)=0</math>, <math>F(50)=1</math>, <math>F(-10)=f(5)=5</math>, <math>F(10)=f(-5)=1</math>, <math>F(-2)=f(-25)+f(-5)f(5)=6</math>, <math>F(2)=f(25)+\binom{f(5)}{2}=16</math>, so we get | We do casework on the (unique) even constant term <math>d\in\{\pm2,\pm10,\pm50\}</math> in our product. For convenience, let <math>F(d)</math> be the number of ways to get a product of <math>50/d</math> without using <math>\pm 1</math> (so only using <math>\pm5,\pm25</math>) and recall <math>f(-1) = 1</math>; then our final answer will be <math>2^{f(1)}\sum_{d\in\{2,10,50\}}(f(-d)+f(d))(F(-d)+F(d))</math>. It's easy to compute <math>F(-50)=0</math>, <math>F(50)=1</math>, <math>F(-10)=f(5)=5</math>, <math>F(10)=f(-5)=1</math>, <math>F(-2)=f(-25)+f(-5)f(5)=6</math>, <math>F(2)=f(25)+\binom{f(5)}{2}=16</math>, so we get | ||
<cmath> 4 [ (1+3)(6+16) + (1+5)(1+5) + (1+7)(0+1) ] = 4[132] = \boxed{\textbf{(B) }528} </cmath> | <cmath> 4 [ (1+3)(6+16) + (1+5)(1+5) + (1+7)(0+1) ] = 4[132] = \boxed{\textbf{(B) }528} </cmath> | ||
+ | |||
+ | ==Solution 2== | ||
+ | |||
+ | Disregard sign; we can tack on <math>x-1</math> if the product ends up being negative. | ||
+ | |||
+ | <math>1: \pm i,-1</math> (2) (1 is not included) | ||
+ | |||
+ | <math>2: \pm 2, \pm 1\pm i</math> (4) | ||
+ | |||
+ | <math>5: \pm 2\pm i, \pm 1\pm 2i, \pm 5</math> (6) | ||
+ | |||
+ | <math>10: \pm 3\pm i, \pm 1\pm 3i, \pm 10</math> (6) | ||
+ | |||
+ | <math>25: \pm 25, \pm 3\pm 4i, \pm 4\pm 3i, \pm 5i</math> (7) | ||
+ | |||
+ | <math>50: \pm 50, \pm 1\pm 7i, \pm7\pm i, \pm 5\pm 5i</math> (8) | ||
+ | |||
+ | Our answer is <math>2^2\left(4\cdot\binom{6}{2}+6\cdot 6+4\cdot 7+8\right)=\boxed{528.}</math> | ||
+ | |||
+ | ==Solution 3== | ||
+ | |||
+ | By Vieta's formula <math>50</math> is the product of all <math>n</math> roots. As the roots are all in the form <math>a + bi</math>, there must exist a conjugate <math>a-bi</math> for each root. | ||
+ | |||
+ | <math>(a+bi)(a-bi) = a^2 + b^2</math> | ||
+ | |||
+ | <math>50 = 2 \cdot 5^2</math> | ||
+ | |||
+ | If <math>a \neq b \neq 0</math>, the roots can be <math>a \pm bi</math>, <math>-a \pm bi</math>, <math>b \pm ai</math>, <math>-b \pm ai</math>, totaling <math>4</math> pairs of roots. | ||
+ | |||
+ | If <math>a = b</math>, the roots can be <math>a \pm ai</math>, <math>-a \pm ai</math>, totaling <math>2</math> pairs of roots. | ||
+ | |||
+ | If <math>a \neq b</math>, <math>b = 0</math>, the roots can be <math>\pm a</math>, <math>\pm ai</math>, totaling <math>2</math> pairs of roots. | ||
+ | |||
+ | <cmath>\begin{align*} | ||
+ | 2 \cdot 25 &= (1^2+1^2)5^2 &: 2 \cdot 2 = 4\\ | ||
+ | 2 \cdot 25 &= 2 \cdot 5^2 &: 2 \cdot 2 = 4\\ | ||
+ | 2 \cdot 25 &= (1^2+1^2) \cdot (3^2+4^2) &: 2 \cdot 4 = 8\\ | ||
+ | 2 \cdot 25 &= 2 \cdot (3^2+4^2) &: 2 \cdot 4 = 8 | ||
+ | \end{align*}</cmath> | ||
+ | |||
+ | <cmath>\begin{align*} | ||
+ | 10 \cdot 5 &= (1^2+3^2)(1^2+2^2) &&: 4 \cdot 4 = 16\\ | ||
+ | 10 \cdot 5 &= 10 \cdot (1^2+2^2) &&: 2 \cdot 4 = 8\\ | ||
+ | 10 \cdot 5 &= (1^2+3^2) \cdot 5 &&: 4 \cdot 2 = 8\\ | ||
+ | 10 \cdot 5 &= 10 \cdot 5 &&: 2 \cdot 2 = 4\\ | ||
+ | \end{align*}</cmath> | ||
+ | |||
+ | <cmath>\begin{align*} | ||
+ | 2 \cdot 5 \cdot 5&= (1^2+1^2)(1^2+2^2)(1^2+2^2) &&: 2 \cdot 4 \cdot 4 = 32\\ | ||
+ | 2 \cdot 5 \cdot 5&= 2 \cdot (1^2+2^2)(1^2+2^2) &&: 2 \cdot 4 \cdot 4 = 32\\ | ||
+ | 2 \cdot 5 \cdot 5&= 2 \cdot 5 \cdot (1^2+2^2) &&: 2 \cdot 2 \cdot 4 = 16\\ | ||
+ | 2 \cdot 5 \cdot 5&= 2 \cdot 5 \cdot 5 &&: 2 \cdot 2 \cdot 2 = 8\\ | ||
+ | 2 \cdot 5 \cdot 5&= (1^2+1^2) \cdot 5 \cdot (1^2+2^2) &&: 2 \cdot 2 \cdot 4 = 16\\ | ||
+ | 2 \cdot 5 \cdot 5&= (1^2+1^2) \cdot 5 \cdot 5 &&: 2 \cdot 2 \cdot 2 = 8\\ | ||
+ | \end{align*}</cmath> | ||
+ | |||
+ | <cmath>\begin{align*} | ||
+ | (1^2+7^2) &: 4\\ | ||
+ | (5^2+5^2) &: 2\\ | ||
+ | 50 &: 2 | ||
+ | \end{align*}</cmath> | ||
+ | |||
+ | <math>4+4+8+8+16+8+8+4+32+32+16+8+16+8+4+2+2 = 176</math> | ||
+ | |||
+ | For each case <math>1^2</math> can be added, yielding 2 more cases <math>(\pm 1, \pm i)</math>. <math>176 \cdot 3 = \boxed{\textbf{(B) }528}</math> | ||
+ | |||
+ | ~[https://artofproblemsolving.com/wiki/index.php/User:Isabelchen isabelchen] | ||
== See also == | == See also == |
Latest revision as of 01:10, 31 December 2022
Problem
Let be the set of polynomials of the form
where
are integers and
has distinct roots of the form
with
and
integers. How many polynomials are in
?
Solution 1
If we factor into irreducible polynomials (in ), each factor
has exponent
in the factorization and degree at most
(since the
with
come in conjugate pairs with product
). Clearly we want the product of constant terms of these polynomials to equal
; for
, let
be the number of permitted
with constant term
. It's easy to compute
,
,
,
,
,
, and obviously
for negative
.
Note that by the distinctness condition, the only constant terms that can be repeated are those with
and
, i.e.
and
. Also, the
s don't affect the product, so we can simply count the number of polynomials with no constant terms of
and multiply by
at the end.
We do casework on the (unique) even constant term in our product. For convenience, let
be the number of ways to get a product of
without using
(so only using
) and recall
; then our final answer will be
. It's easy to compute
,
,
,
,
,
, so we get
Solution 2
Disregard sign; we can tack on if the product ends up being negative.
(2) (1 is not included)
(4)
(6)
(6)
(7)
(8)
Our answer is
Solution 3
By Vieta's formula is the product of all
roots. As the roots are all in the form
, there must exist a conjugate
for each root.
If , the roots can be
,
,
,
, totaling
pairs of roots.
If , the roots can be
,
, totaling
pairs of roots.
If ,
, the roots can be
,
, totaling
pairs of roots.
For each case can be added, yielding 2 more cases
.
See also
2013 AMC 12B (Problems • Answer Key • Resources) | |
Preceded by Problem 24 |
Followed by Last Question |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25 | |
All AMC 12 Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.