2009 AIME II Problems/Problem 9
Problem
Let be the number of solutions in positive integers to the equation , and let be the number of solutions in positive integers to the equation . Find the remainder when is divided by .
Solution
Solution 1
Brute force. It is actually reasonably easy to compute and exactly.
First, note that if , then must be odd. Let . We get , which simplifies to . For any pair of positive integers such that we have exactly one such that the equality holds. Hence we need to count the pairs .
For a fixed , can be at most . Hence the number of solutions is
Similarly, we can compute that , hence .
Solution 2
We can avoid computing and , instead we will compute directly.
Note that if and only if . Hence there is an almost 1-to-1 correspondence between the positive integer solutions of the two equations. The only exceptions are the solutions of the first equation in which at least one of the variables is equal to . The value is the number of such solutions.
If , we get the equation . The variable must be odd, and it must be between and , inclusive. For each such there is exactly one valid . Hence in this case there are valid solutions.
If , we get the equation , or equivalently . The variable must be between and , inclusive, and for each such there is exactly one valid . Hence in this case there are valid solutions.
If , we get the equation . The variable must be odd, thus let . We get , or equivalently, . Again, we see that must be odd, thus let . We get , which simplifies to . Now, we see that must be between and , inclusive, and for each such we have exactly one valid . Hence in this case there are valid solutions.
Finally, we must note that there are two special solutions: one with , and one with . We counted each of them twice, hence we have to subtract two from the total.
Therefore , and the answer is .
Solution 3
Perform a similar operation as in Solution 2, but only on : if and only if . The value is thus the additional solutions we have for this equation as opposed to the second.
The second equation requires to be even, so the largest solution for would be and the smallest . Now let . Note that we can make without problems, and likewise with all the solutions in between; so the only additional solutions for will be below the smallest for . Accordingly, can equal or when or .
So there are only two equations to consider: and , or and .
If , must be between and to obtain positive integer solutions because when ; there is exactly one valid for each .
If , must be between and to obtain positive integer solutions; there is exactly one valid for each .
Therefore .
See Also
2009 AIME II (Problems • Answer Key • Resources) | ||
Preceded by Problem 8 |
Followed by Problem 10 | |
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.