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 "2006 AIME II Problems/Problem 13"

(Undo revision 82061 by MSTang (talk))
 
(6 intermediate revisions by 3 users not shown)
Line 2: Line 2:
 
How many integers <math> N </math> less than <math>1000</math> can be written as the sum of <math> j </math> consecutive positive odd integers from exactly 5 values of <math> j\ge 1 </math>?
 
How many integers <math> N </math> less than <math>1000</math> can be written as the sum of <math> j </math> consecutive positive odd integers from exactly 5 values of <math> j\ge 1 </math>?
  
−
== Solution ==
+
== Solution 1 ==
 
Let the first odd integer be <math>2n+1</math>, <math>n\geq 0</math>. Then the final odd integer is <math>2n+1 + 2(j-1) = 2(n+j) - 1</math>. The odd integers form an [[arithmetic sequence]] with sum <math>N = j\left(\frac{(2n+1) + (2(n+j)-1)}{2}\right) = j(2n+j)</math>. Thus, <math>j</math> is a factor of <math>N</math>.
 
Let the first odd integer be <math>2n+1</math>, <math>n\geq 0</math>. Then the final odd integer is <math>2n+1 + 2(j-1) = 2(n+j) - 1</math>. The odd integers form an [[arithmetic sequence]] with sum <math>N = j\left(\frac{(2n+1) + (2(n+j)-1)}{2}\right) = j(2n+j)</math>. Thus, <math>j</math> is a factor of <math>N</math>.
  
Line 23: Line 23:
 
:Those give <math>10</math> possibilities for even <math>N</math>.
 
:Those give <math>10</math> possibilities for even <math>N</math>.
  
−
The total number of integers <math>N</math> is <math>5 + 10 = \boxed{015}</math>.
+
The total number of integers <math>N</math> is <math>5 + 10 = \boxed{15}</math>.
 +
== Solution 2==
 +
Let the largest odd number below the sequence be the <math>q</math>th positive odd number, and the largest odd number in the sequence be the <math>p</math>th positive odd number. Therefore, the sum is <math>p^2-q^2=(p+q)(p-q)</math> by sum of consecutive odd numbers. Note that <math>p+q</math> and <math>p-q</math> have the same parity, and <math>q</math> can equal <math>0</math>. We then perform casework based on the parity of <math>p-q</math>.  
  
−
==Solution 2==
+
If <math>p-q</math> is odd, then <math>p^2-q^2</math> must always be odd. Therefore, to have 5 pairs of odd factors, we must have either <math>9</math> (in which case the number is a perfect square) or <math>10</math> factors. Considering the upper bound, the only way this can happen is <math>p_1^4\cdot{p_2}</math> or <math>p_1^2\cdot{p_2^2}</math>. N must then be one of
−
It is a well known fact that the sum of the first <math>n</math> odd positive integers is equal to <math>n^2</math>. Let <math>a^2</math> be the sum of the odds from 1 to the integer included in the sum, and let <math>b^2</math> be the sum of odds from 1 to the largest odd less than the interval of length j. (For example, if we start at 5 and have <math> j = 3</math>, <math>a^2 = 1 + 3 + 5 + 7 + 9</math> and <math>b^2 = 1 + 3</math>). Then <math>a^2 - b^2 = 1000</math>, or <math>(a+b)(a-b) = 1000 = 2^3\cdot 5^3</math>. There are <math>4 \cdot 4 = 16</math> factors of 1000, but we want all <math>N < 1000</math>, thus the answer is 15.
+
<cmath>(3^2\cdot5^2),\ (3^2\cdot7^2),\ (3^4\cdot5),\ (3^4\cdot7),\ (3^4\cdot 11)</cmath>
 +
So, there are <math>5</math> solutions when <math>(p+q)(p-q)</math> is odd.
 +
 
 +
If <math>p-q</math> is even, then <math>(p+q)(p-q)</math> must have at least two factors of <math>2</math>, so we can rewrite the expression as <math>4(k)(k-q)</math> where <math>k=\frac{p+q}{2}</math>. We can disregard the <math>4</math> by dividing by <math>4</math> and restricting our upper bound to <math>250</math>. Since <math>k</math> and <math>q</math> don't have to be the same parity, we can include all cases less than 250 that have 9 or 10 factors. We then have
 +
<cmath>(2^2\cdot3^2),(2^2\cdot5^2),(2^2\cdot7^2), (3^2\cdot5^2), (2^4\cdot3), (2^4\cdot5), (2^4\cdot7), (2^4\cdot11), (2^4\cdot13), (3^4\cdot2)</cmath>
 +
as the possibilities.  
  
 +
Therefore, there are <math>10+5=\boxed{015}</math> possibilities for <math>p^2-q^2=N</math> ~sigma
 
== See also ==
 
== See also ==
 
{{AIME box|year=2006|n=II|num-b=12|num-a=14}}
 
{{AIME box|year=2006|n=II|num-b=12|num-a=14}}

Latest revision as of 16:48, 25 October 2024

Problem

How many integers $N$ less than $1000$ can be written as the sum of $j$ consecutive positive odd integers from exactly 5 values of $j\ge 1$?

Solution 1

Let the first odd integer be $2n+1$, $n\geq 0$. Then the final odd integer is $2n+1 + 2(j-1) = 2(n+j) - 1$. The odd integers form an arithmetic sequence with sum $N = j\left(\frac{(2n+1) + (2(n+j)-1)}{2}\right) = j(2n+j)$. Thus, $j$ is a factor of $N$.

Since $n\geq 0$, it follows that $2n+j \geq j$ and $j\leq \sqrt{N}$.

Since there are exactly $5$ values of $j$ that satisfy the equation, there must be either $9$ or $10$ factors of $N$. This means $N=p_1^2p_2^2$ or $N=p_1p_2^4$. Unfortunately, we cannot simply observe prime factorizations of $N$ because the factor $(2n+j)$ does not cover all integers for any given value of $j$.

Instead we do some casework:

  • If $N$ is odd, then $j$ must also be odd. For every odd value of $j$, $2n+j$ is also odd, making this case valid for all odd $j$. Looking at the forms above and the bound of $1000$, $N$ must be

\[(3^2\cdot5^2),\ (3^2\cdot7^2),\ (3^4\cdot5),\ (3^4\cdot7),\ (3^4\cdot 11)\]

Those give $5$ possibilities for odd $N$.
  • If $N$ is even, then $j$ must also be even. Substituting $j=2k$, we get

\[N = 4k(n+k) \Longrightarrow \frac{N}{4} = k(n+k)\]

Now we can just look at all the prime factorizations since $(n+k)$ cover the integers for any $k$. Note that our upper bound is now $250$:

\[\frac{N}{4} = (2^2\cdot3^2),(2^2\cdot5^2),(2^2\cdot7^2), (3^2\cdot5^2), (2^4\cdot3), (2^4\cdot5), (2^4\cdot7), (2^4\cdot11), (2^4\cdot13), (3^4\cdot2)\]

Those give $10$ possibilities for even $N$.

The total number of integers $N$ is $5 + 10 = \boxed{15}$.

Solution 2

Let the largest odd number below the sequence be the $q$th positive odd number, and the largest odd number in the sequence be the $p$th positive odd number. Therefore, the sum is $p^2-q^2=(p+q)(p-q)$ by sum of consecutive odd numbers. Note that $p+q$ and $p-q$ have the same parity, and $q$ can equal $0$. We then perform casework based on the parity of $p-q$.

If $p-q$ is odd, then $p^2-q^2$ must always be odd. Therefore, to have 5 pairs of odd factors, we must have either $9$ (in which case the number is a perfect square) or $10$ factors. Considering the upper bound, the only way this can happen is $p_1^4\cdot{p_2}$ or $p_1^2\cdot{p_2^2}$. N must then be one of \[(3^2\cdot5^2),\ (3^2\cdot7^2),\ (3^4\cdot5),\ (3^4\cdot7),\ (3^4\cdot 11)\] So, there are $5$ solutions when $(p+q)(p-q)$ is odd.

If $p-q$ is even, then $(p+q)(p-q)$ must have at least two factors of $2$, so we can rewrite the expression as $4(k)(k-q)$ where $k=\frac{p+q}{2}$. We can disregard the $4$ by dividing by $4$ and restricting our upper bound to $250$. Since $k$ and $q$ don't have to be the same parity, we can include all cases less than 250 that have 9 or 10 factors. We then have \[(2^2\cdot3^2),(2^2\cdot5^2),(2^2\cdot7^2), (3^2\cdot5^2), (2^4\cdot3), (2^4\cdot5), (2^4\cdot7), (2^4\cdot11), (2^4\cdot13), (3^4\cdot2)\] as the possibilities.

Therefore, there are $10+5=\boxed{015}$ possibilities for $p^2-q^2=N$ ~sigma

See also

2006 AIME II (Problems • Answer Key • Resources)
Preceded by
Problem 12 		Followed by
Problem 14
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=2006_AIME_II_Problems/Problem_13&oldid=230642"