Difference between revisions of "2010 AIME II Problems/Problem 10"
m (→Solution 1) |
|||
| Line 30: | Line 30: | ||
===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>. | 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> | ||
== See also == | == See also == | ||
Revision as of 22:36, 15 October 2022
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, 
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. 
