2018 AIME I Problems/Problem 1
Contents
Problem 1
Let be the number of ordered pairs of integers with and such that the polynomial can be factored into the product of two (not necessarily distinct) linear factors with integer coefficients. Find the remainder when is divided by .
Solution
You let the linear factors be as .
Then, obviously and .
We know that and , so and both have to be non-negative
However, cannot be , so at least one of and must be greater than , ie positive.
Also, cannot be greater than , so must be less than or equal to .
Essentially, if we plot the solutions, we get a triangle on the coordinate plane with vertices and . Remember that does not work, so there is a square with top right corner .
Note that and are interchangeable, since they end up as and in the end anyways. Thus, we simply draw a line from to , designating one of the halves as our solution (since the other side is simply the coordinates flipped).
We note that the pattern from to is solutions and from to is solutions, since we can decrease the -value by until for each coordinate.
Adding up gives This gives us , and
Thus, the answer is:
Solution 2
Similar to the previous problem, we plot the triangle and cut it in half. Then, we find the number of boundary points, which is 100+51+51-3, or just 200. Using Pick's theorem, we know that the area of the half-triangle, which is 2500, is just I+100-1. That means that there are 2401 interior points, plus 200 boundary points, which is 2601. However, (0,0) does not work, so the answer is
Solution 3 (less complicated)
Notice that for to be true, for every , will always be the product of the possibilities of how to add two integers to . For example, if , will be the product of and , as those two sets are the only possibilities of adding two integers to . Note that order does not matter. If we just do some simple casework, we find out that:
if is odd, there will always be possibilities of adding two integers to .
if is even, there will always be possibilities of adding two integers to .
Using the casework, we have possibilities. This will mean that the answer is possibilities.
Thus, our solution is .
Solution by IronicNinja~
Solution 3
Let's write the linear factors as .
Then we can write them as: .
or has to be a positive integer as a cannot be 0.
has to be between and , as a cannot be over .
Excluding , we can see there is always a pair of a-values for a certain amount of b-values.
For instance, and both have b-values. and both have b-values.
We notice the pattern of the number of b-values in relation to the a-values:
The following link is the URL to the graph I drew showing the relationship between a-values and b-values http://artofproblemsolving.com/wiki/index.php?title=File:Screen_Shot_2018-04-30_at_8.15.00_PM.png#file
The pattern continues until , and in total, there are pairs of a-value with the same amount of b-values. The two lone a-values without a pair are, the (, amount of b-values=1) in the beginning, and (, amount of b-values=51) in the end.
Then, we add numbers from the opposite ends of the spectrum, and quickly notice that there are pairs each with a sum of . gives ordered pairs:
When divided by , it gives the remainder , the answer.
Solution provided by- Yonglao
See Also
2018 AIME I (Problems • Answer Key • Resources) | ||
Preceded by First Problem |
Followed by Problem 2 | |
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.