2010 AIME II Problems/Problem 10
Problem
Find the number of second-degree polynomials with integer coefficients and integer zeros for which .
Contents
[hide]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 r=s is the only case where the polynomials are being overcounted is because of this: We have the four configurations listed below:
(a,r,s) (a,-r,-s) (-a,-r,s) (-a,r,-s)
And notice, we start by counting all the positive solutions. So r and s must be strictly positive, no 0 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 x term would have coefficients that are always different, and because of the negative r and s. Since the a is never equal, these can never create equal x coefficients. We don't need to worry about this as r and s are positive and so that won't have any chance.
However with the (-a,-r,s) and (-a,r,-s), we have the coefficients of the x term as and . In other words, they are equal if or . Well if r=1, then we have s=1 and in the (r,-s) case we (1,-1) and if we transform using (s,-r), then we have (-1, 1). 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 (-1,1) and (1,-1) twice as they will create equal sums. This is why we subtract 1 from .
Each different transformation will give us different coordinates (a,r,s)... it is just that some of them create equal coefficients for the x-term, and we see that they are equal only in this case by our exploration, so we subtract 1 to account and get 163.
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 .
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.