Difference between revisions of "2009 AIME II Problems/Problem 9"
Aops turtle (talk | contribs) m (→Solution 1) |
(Tag: Undo) |
||
(4 intermediate revisions by 2 users not shown) | |||
Line 29: | Line 29: | ||
</cmath> | </cmath> | ||
− | Similarly, we can compute that <math>n=82834</math>, hence <math> | + | Similarly, we can compute that <math>n=82834</math>, hence <math>m-n = 1000 \equiv \boxed{000} \pmod{1000}</math>. |
=== Solution 2 === | === Solution 2 === | ||
Line 56: | Line 56: | ||
<math>4x+9+2z=2009</math> simplifies to <math>2x+z=1000</math>. There is exactly one valid <math>z</math> for each <math>x</math>; <math>x</math> must be between <math>1</math> and <math>499</math> (inclusive) to obtain positive integer solutions. Therefore, there are <math>499</math> solutions in this case. | <math>4x+9+2z=2009</math> simplifies to <math>2x+z=1000</math>. There is exactly one valid <math>z</math> for each <math>x</math>; <math>x</math> must be between <math>1</math> and <math>499</math> (inclusive) to obtain positive integer solutions. Therefore, there are <math>499</math> solutions in this case. | ||
− | Thus, <math>m-n = 501 + 499 = 1000; 1000 \ | + | Thus, <math>m-n = 501 + 499 = 1000; 1000 \equiv \boxed{000} \pmod{1000}</math>. |
== See Also == | == See Also == |
Latest revision as of 15:45, 28 December 2020
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
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
In this solution we will perform a similar operation as in Solution 2, but only on :
if and only if
. There is a one-to-one correspondence between the solutions of these two equations. Let
and require
to be positive as well. Then the second equation becomes
. Notice that there are several "extra" solutions in the first equation that cannot be included in the second equation (since that would make
non-positive). The value
is therefore the number of "extra" solutions.
Since , in order for
to be non-positive
. However, equation (1) requires y to be odd, so we have two cases to consider:
and
. This results in the two equations
and
.
simplifies to
. There is exactly one valid
for each
;
must be between
and
(inclusive) to obtain positive integer solutions. Therefore, there are
solutions in this case.
simplifies to
. There is exactly one valid
for each
;
must be between
and
(inclusive) to obtain positive integer solutions. Therefore, there are
solutions in this case.
Thus, .
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.