2009 AIME II Problems/Problem 7
Problem
Define to be
for
odd and
for
even. When
is expressed as a fraction in lowest terms, its denominator is
with
odd. Find
.
Solution
First, note that , and that
.
We can now take the fraction and multiply both the numerator and the denominator by
. We get that this fraction is equal to
.
Now we can recognize that is simply
, hence this fraction is
, and our sum turns into
.
Let .
Obviously
is an integer, and
can be written as
.
Hence if
is expressed as a fraction in lowest terms, its denominator will be of the form
for some
.
In other words, we just showed that .
To determine
, we need to determine the largest power of
that divides
.
Let be the largest
such that
that divides
.
We can now return to the observation that . Together with the obvious fact that
is odd, we get that
.
It immediately follows that ,
and hence
.
Obviously, for the function
is is a strictly decreasing function.
Therefore
.
We can now compute .
Hence
.
And thus we have , and the answer is
.
Additionally, once you count the number of factors of 2 in the summation, one can consider the fact that, since must be odd, it has to take on a value of
(Because the number of 2s in the summation is clearly greater than
, dividing by
will yield a number greater than 100, and multiplying this number by any odd number greater than
will yield an answer
, which cannot happen on the AIME.) Once you calculate the value of
, and divide by
,
must be equal to 1, as any other value of b will result in an answer >999. This gives
as the answer.
See Also
2009 AIME II (Problems • Answer Key • Resources) | ||
Preceded by Problem 6 |
Followed by Problem 8 | |
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.