2005 AIME I Problems/Problem 12
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
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 ).
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 .
Similarly, , where the accounts for those numbers between and .
Then, . We can apply the formula . From this formula, it follows that and so that
- . Thus,
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
|2005 AIME I (Problems • Answer Key • Resources)|
|1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15|
|All AIME Problems and Solutions|