Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2005 AIME I Problems/Problem 12"
 
(10 intermediate revisions by 5 users not shown)
Line 2: Line 2:
 
For [[positive integer]]s <math> n, </math> let <math> \tau (n) </math> denote the number of positive integer [[divisor]]s of <math> n, </math> including 1 and <math> n. </math> For example, <math> \tau (1)=1 </math> and <math> \tau(6) =4. </math> Define <math> S(n) </math> by <math> S(n)=\tau(1)+ \tau(2) + \cdots + \tau(n). </math> Let <math> a </math> denote the number of positive integers <math> n \leq 2005 </math> with <math> S(n) </math> [[odd integer | odd]], and let <math> b </math> denote the number of positive integers <math> n \leq 2005 </math> with <math> S(n) </math> [[even integer | even]]. Find <math> |a-b|. </math>
 
For [[positive integer]]s <math> n, </math> let <math> \tau (n) </math> denote the number of positive integer [[divisor]]s of <math> n, </math> including 1 and <math> n. </math> For example, <math> \tau (1)=1 </math> and <math> \tau(6) =4. </math> Define <math> S(n) </math> by <math> S(n)=\tau(1)+ \tau(2) + \cdots + \tau(n). </math> Let <math> a </math> denote the number of positive integers <math> n \leq 2005 </math> with <math> S(n) </math> [[odd integer | odd]], and let <math> b </math> denote the number of positive integers <math> n \leq 2005 </math> with <math> S(n) </math> [[even integer | even]]. Find <math> |a-b|. </math>
  
−
== Solution ==
+
__TOC__
 +
== 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.  
  
 
So, for a given <math>n</math>, if we choose the positive integer <math>m</math> such that <math>m^2 \leq n < (m + 1)^2</math> we see that <math>S(n)</math> has the same parity as <math>m</math>.   
 
So, for a given <math>n</math>, if we choose the positive integer <math>m</math> such that <math>m^2 \leq n < (m + 1)^2</math> we see that <math>S(n)</math> has the same parity as <math>m</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>).
  
−
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, and that these are the only such numbers less than <math>2007</math> (because <math>45^2 = 2025 > 2007</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>.
 +
 
 +
== 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>.
  
 
Thus <math>a = (2^2 - 1^2) + (4^2 - 3^2) + \ldots + (44^2 - 43^2)</math>.
 
Thus <math>a = (2^2 - 1^2) + (4^2 - 3^2) + \ldots + (44^2 - 43^2)</math>.
  
−
Similarly, <math>b = (3^2 - 2^2) + (5^2 - 4^2) + \ldots + (45^2 - 44^2) - 17</math>, where the <math>-17</math> accounts for those numbers between <math>2007</math> and <math>2024</math>.
+
Then, <math>|a - b| = |2(2^2 + 4^2 + \ldots + 44^2) - 2(1^2 + 3^2 + 5^2 + \ldots 43^2) + 1^2 - 45^2 + 19|</math>.
 +
We can apply the formula <math>1^2 + 2^2 + \ldots + n^2 = \frac{n(n + 1)(2n + 1)}{6}</math>.  From this formula, it follows that <math>2^2 + 4^2 + \ldots + (2n)^2 = \frac{2n(n + 1)(2n + 1)}{3}</math> and so that
 +
:<math>1^2 + 3^2 + \ldots +(2n + 1)^2 = (1^2 + 2^2 + \ldots +(2n + 1)^2) - (2^2 + 4^2 + \ldots + (2n)^2)</math>
 +
:<math>= \frac{(2n + 1)(2n + 2)(4n + 3)}{6} - \frac{2n(n + 1)(2n + 1)}{3} = \frac{(n + 1)(2n + 1)(2n + 3)}{3}</math>.  Thus,
 +
 
 +
<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
  
−
Then <math>|a - b| = |2(2^2 + 4^2 + \ldots + 44^2) - 2(1^2 + 3^2 + 5^2 + \ldots 43^2) + 1^2 - 45^2 + 17|</math>.
+
<math>a = (2^2-1^2) + (4^2-3^2) \dots (44^2 - 43^2) = (2+1)(2-1)+(4+3)(4-3) \dots (44+43)(44-43) = 1+2+3...44 = \Delta 44</math>.  
  
 +
<math>b = 3^2-2^2+5^2-4^2...2006-44^2 = (3+2)(3-2) \dots (43+42)(43-42) + 1 + (2005 - 44^2) = \Delta 43 + 69</math>.
  
−
We must now apply the formula <math>1^2 + 2^2 + \ldots + n^2 = \frac{n(n + 1)(2n + 1)}{6}</math>. From this formula, it follows that <math>2^2 + 4^2 + \ldots + (2n)^2 = \frac{2n(n + 1)(2n + 1)}{3}</math> and so that <math>1^2 + 3^2 + \ldots +(2n + 1)^2 = (1^2 + 2^2 + \ldots +(2n + 1)^2) - (2^2 + 4^2 + \ldots + (2n)^2) = \frac{(2n + 1)(2n + 2)(4n + 3)}{6} - \frac{2n(n + 1)(2n + 1)}{3} = \frac{(n + 1)(2n + 1)(2n + 3)}{3}</math>.  Thus,
+
<math>a-b = \Delta 44-\Delta 43-69 = 44-69 = -25</math>. They ask for <math>|a-b|</math>, so our answer is <math>|-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 + 18\right| = |-27| = 027</math>.
+
-Alexlikemath
  
 
== See also ==
 
== See also ==
−
* [[2005 AIME I Problems/Problem 13 | Next problem]]
+
{{AIME box|year=2005|n=I|num-b=11|num-a=13}}
−
* [[2005 AIME I Problems/Problem 11 | Previous problem]]
 
−
* [[2005 AIME I Problems]]
 
  
 
[[Category:Intermediate Number Theory Problems]]
 
[[Category:Intermediate Number Theory Problems]]
 +
{{MAA Notice}}

Latest revision as of 01:29, 4 May 2021

Problem

For positive integers $n,$ let $\tau (n)$ denote the number of positive integer divisors of $n,$ including 1 and $n.$ For example, $\tau (1)=1$ and $\tau(6) =4.$ Define $S(n)$ by $S(n)=\tau(1)+ \tau(2) + \cdots + \tau(n).$ Let $a$ denote the number of positive integers $n \leq 2005$ with $S(n)$ odd, and let $b$ denote the number of positive integers $n \leq 2005$ with $S(n)$ even. Find $|a-b|.$

Solution 1

It is well-known that $\tau(n)$ is odd if and only if $n$ is a perfect square. (Otherwise, we can group divisors into pairs whose product is $n$.) Thus, $S(n)$ is odd if and only if there are an odd number of perfect squares less than $n$. So $S(1), S(2)$ and $S(3)$ are odd, while $S(4), S(5), \ldots, S(8)$ are even, and $S(9), \ldots, S(15)$ are odd, and so on.

So, for a given $n$, if we choose the positive integer $m$ such that $m^2 \leq n < (m + 1)^2$ we see that $S(n)$ has the same parity as $m$.

It follows that the numbers between $1^2$ and $2^2$, between $3^2$ and $4^2$, and so on, all the way up to the numbers between $43^2$ and $44^2 = 1936$ have $S(n)$ odd. These are the only such numbers less than $2005$ (because $45^2 = 2025 > 2005$).

Solution 2

Notice that the difference between consecutive squares are consecutively increasing odd numbers. Thus, there are $3$ numbers between $1$ (inclusive) and $4$ (exclusive), $5$ numbers between $4$ and $9$, and so on. The number of numbers from $n^2$ to $(n + 1)^2$ is $(n + 1 - n)(n + 1 + n) = 2n + 1$. Whenever the lowest square beneath a number is odd, the parity will be odd, and the same for even. Thus, $a = [2(1) + 1] + [2(3) + 1] \ldots [2(43) + 1] = 3 + 7 + 11 \ldots 87$. $b = [2(2) + 1] + [2(4) + 1] \ldots [2(42) + 1] + 70 = 5 + 9 \ldots 85 + 70$, the $70$ accounting for the difference between $2005$ and $44^2 = 1936$, inclusive. Notice that if we align the two and subtract, we get that each difference is equal to $2$. Thus, the solution is $|a - b| = |b - a| = |2 \cdot 21 + 70 - 87| = \boxed{025}$.

Solution 3

Similarly, $b = (3^2 - 2^2) + (5^2 - 4^2) + \ldots + (45^2 - 44^2) - 19$, where the $-19$ accounts for those numbers between $2005$ and $2024$.

Thus $a = (2^2 - 1^2) + (4^2 - 3^2) + \ldots + (44^2 - 43^2)$.

Then, $|a - b| = |2(2^2 + 4^2 + \ldots + 44^2) - 2(1^2 + 3^2 + 5^2 + \ldots 43^2) + 1^2 - 45^2 + 19|$. We can apply the formula $1^2 + 2^2 + \ldots + n^2 = \frac{n(n + 1)(2n + 1)}{6}$. From this formula, it follows that $2^2 + 4^2 + \ldots + (2n)^2 = \frac{2n(n + 1)(2n + 1)}{3}$ and so that

$1^2 + 3^2 + \ldots +(2n + 1)^2 = (1^2 + 2^2 + \ldots +(2n + 1)^2) - (2^2 + 4^2 + \ldots + (2n)^2)$
$= \frac{(2n + 1)(2n + 2)(4n + 3)}{6} - \frac{2n(n + 1)(2n + 1)}{3} = \frac{(n + 1)(2n + 1)(2n + 3)}{3}$. Thus,

$|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}$.

Solution 4

Let $\Delta n$ denote the sum $1+2+3+ \dots +n-1+n$. We can easily see from the fact "It is well-known that $\tau(n)$ is odd if and only if $n$ is a perfect square.", that

$a = (2^2-1^2) + (4^2-3^2) \dots (44^2 - 43^2) = (2+1)(2-1)+(4+3)(4-3) \dots (44+43)(44-43) = 1+2+3...44 = \Delta 44$.

$b = 3^2-2^2+5^2-4^2...2006-44^2 = (3+2)(3-2) \dots (43+42)(43-42) + 1 + (2005 - 44^2) = \Delta 43 + 69$.

$a-b = \Delta 44-\Delta 43-69 = 44-69 = -25$. They ask for $|a-b|$, so our answer is $|-25| = \boxed{025}$

-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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2005_AIME_I_Problems/Problem_12&oldid=153188"