Difference between revisions of "2005 AIME I Problems/Problem 12"
Alexlikemath (talk | contribs) (→Solution) |
|||
Line 3: | Line 3: | ||
__TOC__ | __TOC__ | ||
− | == Solution == | + | == Solution 1== |
It is well-known that <math>\tau(n)</math> is odd if and only if <math>n</math> is a [[perfect square]]. (Otherwise, we can group [[divisor]]s into pairs whose product is <math>n</math>.) Thus, <math>S(n)</math> is odd if and only if there are an odd number of perfect squares less than <math>n</math>. So <math>S(1), S(2)</math> and <math>S(3)</math> are odd, while <math>S(4), S(5), \ldots, S(8)</math> are even, and <math>S(9), \ldots, S(15)</math> are odd, and so on. | It is well-known that <math>\tau(n)</math> is odd if and only if <math>n</math> is a [[perfect square]]. (Otherwise, we can group [[divisor]]s into pairs whose product is <math>n</math>.) Thus, <math>S(n)</math> is odd if and only if there are an odd number of perfect squares less than <math>n</math>. So <math>S(1), S(2)</math> and <math>S(3)</math> are odd, while <math>S(4), S(5), \ldots, S(8)</math> are even, and <math>S(9), \ldots, S(15)</math> are odd, and so on. | ||
Line 10: | Line 10: | ||
It follows that the numbers between <math>1^2</math> and <math>2^2</math>, between <math>3^2</math> and <math>4^2</math>, and so on, all the way up to the numbers between <math>43^2</math> and <math>44^2 = 1936</math> have <math>S(n)</math> odd. These are the only such numbers less than <math>2005</math> (because <math>45^2 = 2025 > 2005</math>). | It follows that the numbers between <math>1^2</math> and <math>2^2</math>, between <math>3^2</math> and <math>4^2</math>, and so on, all the way up to the numbers between <math>43^2</math> and <math>44^2 = 1936</math> have <math>S(n)</math> odd. These are the only such numbers less than <math>2005</math> (because <math>45^2 = 2025 > 2005</math>). | ||
− | + | == Solution 2 == | |
Notice that the difference between consecutive squares are consecutively increasing odd numbers. Thus, there are <math>3</math> numbers between <math>1</math> (inclusive) and <math>4</math> (exclusive), <math>5</math> numbers between <math>4</math> and <math>9</math>, and so on. The number of numbers from <math>n^2</math> to <math>(n + 1)^2</math> is <math>(n + 1 - n)(n + 1 + n) = 2n + 1</math>. Whenever the lowest square beneath a number is odd, the parity will be odd, and the same for even. Thus, <math>a = [2(1) + 1] + [2(3) + 1] \ldots [2(43) + 1] = 3 + 7 + 11 \ldots 87</math>. <math>b = [2(2) + 1] + [2(4) + 1] \ldots [2(42) + 1] + 70 = 5 + 9 \ldots 85 + 70</math>, the <math>70</math> accounting for the difference between <math>2005</math> and <math>44^2 = 1936</math>, inclusive. Notice that if we align the two and subtract, we get that each difference is equal to <math>2</math>. Thus, the solution is <math>|a - b| = |b - a| = |2 \cdot 21 + 70 - 87| = \boxed{025}</math>. | Notice that the difference between consecutive squares are consecutively increasing odd numbers. Thus, there are <math>3</math> numbers between <math>1</math> (inclusive) and <math>4</math> (exclusive), <math>5</math> numbers between <math>4</math> and <math>9</math>, and so on. The number of numbers from <math>n^2</math> to <math>(n + 1)^2</math> is <math>(n + 1 - n)(n + 1 + n) = 2n + 1</math>. Whenever the lowest square beneath a number is odd, the parity will be odd, and the same for even. Thus, <math>a = [2(1) + 1] + [2(3) + 1] \ldots [2(43) + 1] = 3 + 7 + 11 \ldots 87</math>. <math>b = [2(2) + 1] + [2(4) + 1] \ldots [2(42) + 1] + 70 = 5 + 9 \ldots 85 + 70</math>, the <math>70</math> accounting for the difference between <math>2005</math> and <math>44^2 = 1936</math>, inclusive. Notice that if we align the two and subtract, we get that each difference is equal to <math>2</math>. Thus, the solution is <math>|a - b| = |b - a| = |2 \cdot 21 + 70 - 87| = \boxed{025}</math>. | ||
− | + | == Solution 3 == | |
Similarly, <math>b = (3^2 - 2^2) + (5^2 - 4^2) + \ldots + (45^2 - 44^2) - 19</math>, where the <math>-19</math> accounts for those numbers between <math>2005</math> and <math>2024</math>. | Similarly, <math>b = (3^2 - 2^2) + (5^2 - 4^2) + \ldots + (45^2 - 44^2) - 19</math>, where the <math>-19</math> accounts for those numbers between <math>2005</math> and <math>2024</math>. | ||
Line 25: | Line 25: | ||
<math>|a - b| = \left| 2\cdot \frac{44\cdot23\cdot45}{3} - 2\cdot \frac{22 \cdot 43 \cdot 45}{3} - 45^2 + 20\right| = |-25| =\boxed{025}</math>. | <math>|a - b| = \left| 2\cdot \frac{44\cdot23\cdot45}{3} - 2\cdot \frac{22 \cdot 43 \cdot 45}{3} - 45^2 + 20\right| = |-25| =\boxed{025}</math>. | ||
− | + | == Solution 4 == | |
Let <math>\Delta n</math> denote the sum <math>1+2+3+ \dots +n-1+n</math>. We can easily see from the fact "It is well-known that <math>\tau(n)</math> is odd if and only if <math>n</math> is a perfect square.", that | Let <math>\Delta n</math> denote the sum <math>1+2+3+ \dots +n-1+n</math>. We can easily see from the fact "It is well-known that <math>\tau(n)</math> is odd if and only if <math>n</math> is a perfect square.", that | ||
Latest revision as of 01:29, 4 May 2021
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 1
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 2
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 3
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 4
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.