2005 AIME I Problems/Problem 12
Problem
For positive integers let denote the number of positive integer divisors of including 1 and For example, and Define by Let denote the number of positive integers with odd, and let denote the number of positive integers with even. Find
Solution
It is well-known that is odd if and only if is a perfect square. (Otherwise, we can group divisors into pairs whose product is .) Thus, is odd if and only if there are an odd number of perfect squares less than . So and are odd, while are even, and are odd, and so on.
So, for a given , if we choose the positive integer such that we see that has the same parity as .
It follows that the numbers between and , between and , and so on, all the way up to the numbers between and have odd. These are the only such numbers less than (because ).
Solution 1
Notice that the difference between consecutive squares are consecutively increasing odd numbers. Thus, there are numbers between (inclusive) and (exclusive), numbers between and , and so on. The number of numbers from to is . Whenever the lowest square beneath a number is odd, the parity will be odd, and the same for even. Thus, . , the accounting for the difference between and , inclusive. Notice that if we align the two and subtract, we get that each difference is equal to . Thus, the solution is .
Solution 2
Similarly, , where the accounts for those numbers between and .
Thus .
Then, . We can apply the formula . From this formula, it follows that and so that
- . Thus,
.
Solution 3
Let denote the sum . We can easily see from the fact "It is well-known that is odd if and only if is a perfect square.", that
.
.
. They ask for , so our answer is
-Alexlikemath
See also
2005 AIME I (Problems • Answer Key • Resources) | ||
Preceded by Problem 11 |
Followed by Problem 13 | |
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.