Difference between revisions of "2010 AIME II Problems/Problem 10"
m (Semi-automated contest formatting - script by azjps) |
m |
||
(20 intermediate revisions by 9 users not shown) | |||
Line 1: | Line 1: | ||
+ | __TOC__ | ||
+ | |||
== Problem == | == Problem == | ||
Find the number of second-degree [[polynomial]]s <math>f(x)</math> with integer [[coefficient]]s and integer zeros for which <math>f(0)=2010</math>. | Find the number of second-degree [[polynomial]]s <math>f(x)</math> with integer [[coefficient]]s and integer zeros for which <math>f(0)=2010</math>. | ||
− | |||
==Solution== | ==Solution== | ||
===Solution 1=== | ===Solution 1=== | ||
Line 8: | Line 9: | ||
We must now consider the various cases of signs. For the <math>40</math> cases where <math>|r|\neq |s|</math>, there are a total of four possibilities, For the case <math>|r|=|s|=1</math>, there are only three possibilities, <math>(r,s) = (1,1); (1,-1); (-1,-1)</math> as <math>(-1,1)</math> is not distinguishable from the second of those three. | We must now consider the various cases of signs. For the <math>40</math> cases where <math>|r|\neq |s|</math>, there are a total of four possibilities, For the case <math>|r|=|s|=1</math>, there are only three possibilities, <math>(r,s) = (1,1); (1,-1); (-1,-1)</math> as <math>(-1,1)</math> is not distinguishable from the second of those three. | ||
+ | |||
+ | You may ask: How can one of <math>{r, s}</math> be positive and the other negative? <math>a</math> will be negative as a result. That way, it's still <math>+2010</math> that gets multiplied. | ||
Thus the grand total is <math>4\cdot40 + 3 = \boxed{163}</math>. | Thus the grand total is <math>4\cdot40 + 3 = \boxed{163}</math>. | ||
+ | |||
+ | Note: The only reason why we can be confident that <math>r = s</math> is the only case where the polynomials are being overcounted is because of this: We have the four configurations listed below: | ||
+ | |||
+ | <math>(a,r,s)\\ | ||
+ | (a,-r,-s)\\ | ||
+ | (-a,-r,s)\\ | ||
+ | (-a,r,-s)</math> | ||
+ | |||
+ | And notice, we start by counting all the positive solutions. So <math>r</math> and <math>s</math> must be strictly positive, no <math>0</math> or negatives allowed. The negative transformations will count those numbers. | ||
+ | |||
+ | So with these we can conclude that only the first and second together have a chance of being equal, and the third and fourth together. If we consider the first and second, the <math>x</math> term would have coefficients that are always different, <math>-a(r + s)</math> and <math>a(r + s)</math> because of the negative <math>r</math> and <math>s</math>. Since the <math>a</math> is never equal, these can never create equal <math>x</math> coefficients. We don't need to worry about this as <math>r</math> and <math>s</math> are positive and so that won't have any chance. | ||
+ | |||
+ | However with the <math>(-a,-r,s)</math> and <math>(-a,r,-s)</math>, we have the coefficients of the <math>x</math> term as <math>a(s-r)</math> and <math>a(r-s)</math>. In other words, they are equal if <math>s-r=r-s</math> or <math>r=s</math>. Well if <math>r = 1</math>, then we have <math>s = 1</math> and in the <math>(r,-s)</math> case we have <math>(1,-1)</math> and if we transform using <math>(s,-r)</math>, then we have <math>(-1, 1)</math>. So this is the only way that we could possibly overcount the equal cases, and so we need to make sure we don't count <math>(-1,1)</math> and <math>(1,-1)</math> twice as they will create equal sums. This is why we subtract <math>1</math> from <math>41*4=164</math>. | ||
+ | |||
+ | Each different transformation will give us different coordinates <math>(a,r,s)...</math> it is just that some of them create equal coefficients for the <math>x</math>-term, and we see that they are equal only in this case by our exploration, so we subtract <math>1</math> to account and get <math>163</math>. | ||
===Solution 2=== | ===Solution 2=== | ||
− | + | We use [[Burnside's Lemma]]. The set being acted upon is the set of integer triples <math>(a,r,s)</math> such that <math>ars=2010</math>. Because <math>r</math> and <math>s</math> are indistinguishable, the permutation group consists of the identity and the permutation that switches <math>r</math> and <math>s</math>. In cycle notation, the group consists of <math>(a)(r)(s)</math> and <math>(a)(r \: s)</math>. There are <math>4 \cdot 3^4</math> fixed points of the first permutation (after distributing the primes among <math>a</math>, <math>r</math>, <math>s</math> and then considering their signs. We have 4 ways since we can keep them all positive, first 2 negative, first and third negative, or last two negative) and <math>2</math> fixed points of the second permutation (<math>r=s=\pm 1</math>). By Burnside's Lemma, there are <math>\frac{1}{2} (4 \cdot 3^4+2)= \boxed{163}</math> distinguishable triples <math>(a,r,s)</math>. | |
+ | Note: The permutation group is isomorphic to <math>\mathbb{Z}/2\mathbb{Z}</math>. | ||
+ | |||
+ | ==Solution 3== | ||
+ | |||
+ | The equation can be written in the form of <math>k(x-a)(x-b)</math>, where <math>|k|</math> is a divisor of <math>2010</math>. Factor <math>2010=2\cdot 3\cdot 5\cdot 67</math>. We divide into few cases to study. | ||
+ | |||
+ | Firstly, if <math>|k|=1</math>, the equation can be <math>-(x-a)(x+b)</math> or <math>(x-a)(x-b)</math> or <math>(x+a)(x+b)</math>, there are <math>2^4+2^4=32</math> ways | ||
+ | |||
+ | If <math>|k|\in \{2,3,5,67\}</math>. Take <math>|k|=2</math> as an example, follow the procedure above, there are <math>2^3+2^3=16</math> ways, and there are <math>\binom {4}{1}=4</math> ways to choose <math>|k|</math>, so there are <math>16\cdot 4=64</math> ways | ||
+ | |||
+ | |||
+ | If <math>|k|</math> is the product of two factors of <math>2010</math>, there are <math>8</math> ways for each. Thus there are <math>\binom {4}{2}\cdot 8=48</math> ways | ||
+ | |||
+ | If <math>|k|</math> is the product of three factors of <math>2010</math>, there are <math>\binom {4}{3}\cdot 4=16</math> ways | ||
+ | |||
+ | In the end, <math>|k|=2010</math>, only <math>2010(x-1)(x-1); 2010(x+1)(x+1); -2010(x-1)(x+1)</math> work, there are <math>3</math> ways | ||
+ | |||
+ | Thus, <math>32+64+48+16+3=\boxed{163}</math> | ||
+ | |||
+ | ~bluesoul | ||
== See also == | == See also == | ||
Line 18: | Line 56: | ||
[[Category:Intermediate Algebra Problems]] | [[Category:Intermediate Algebra Problems]] | ||
+ | {{MAA Notice}} |
Latest revision as of 16:01, 16 September 2023
Problem
Find the number of second-degree polynomials with integer coefficients and integer zeros for which
.
Solution
Solution 1
Let . Then
. First consider the case where
and
(and thus
) are positive. There are
ways to split up the prime factors between
,
, and
. However,
and
are indistinguishable. In one case,
, we have
. The other
cases are double counting, so there are
.
We must now consider the various cases of signs. For the cases where
, there are a total of four possibilities, For the case
, there are only three possibilities,
as
is not distinguishable from the second of those three.
You may ask: How can one of be positive and the other negative?
will be negative as a result. That way, it's still
that gets multiplied.
Thus the grand total is .
Note: The only reason why we can be confident that is the only case where the polynomials are being overcounted is because of this: We have the four configurations listed below:
And notice, we start by counting all the positive solutions. So and
must be strictly positive, no
or negatives allowed. The negative transformations will count those numbers.
So with these we can conclude that only the first and second together have a chance of being equal, and the third and fourth together. If we consider the first and second, the term would have coefficients that are always different,
and
because of the negative
and
. Since the
is never equal, these can never create equal
coefficients. We don't need to worry about this as
and
are positive and so that won't have any chance.
However with the and
, we have the coefficients of the
term as
and
. In other words, they are equal if
or
. Well if
, then we have
and in the
case we have
and if we transform using
, then we have
. So this is the only way that we could possibly overcount the equal cases, and so we need to make sure we don't count
and
twice as they will create equal sums. This is why we subtract
from
.
Each different transformation will give us different coordinates it is just that some of them create equal coefficients for the
-term, and we see that they are equal only in this case by our exploration, so we subtract
to account and get
.
Solution 2
We use Burnside's Lemma. The set being acted upon is the set of integer triples such that
. Because
and
are indistinguishable, the permutation group consists of the identity and the permutation that switches
and
. In cycle notation, the group consists of
and
. There are
fixed points of the first permutation (after distributing the primes among
,
,
and then considering their signs. We have 4 ways since we can keep them all positive, first 2 negative, first and third negative, or last two negative) and
fixed points of the second permutation (
). By Burnside's Lemma, there are
distinguishable triples
.
Note: The permutation group is isomorphic to
.
Solution 3
The equation can be written in the form of , where
is a divisor of
. Factor
. We divide into few cases to study.
Firstly, if , the equation can be
or
or
, there are
ways
If . Take
as an example, follow the procedure above, there are
ways, and there are
ways to choose
, so there are
ways
If is the product of two factors of
, there are
ways for each. Thus there are
ways
If is the product of three factors of
, there are
ways
In the end, , only
work, there are
ways
Thus,
~bluesoul
See also
2010 AIME II (Problems • Answer Key • Resources) | ||
Preceded by Problem 9 |
Followed by Problem 11 | |
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.