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"

(Added (possibly convoluted) Solution)
(fmtting)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
−
How many integers <math> N </math> less than 1000 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 ==
−
Let the first odd integer be <math>2n+1</math> with <math>n\geq 0</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>.
−
 
 
−
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>j\left(\frac{(2n+1) + (2(n+j)-1)}{2}\right) = j(2n+j)</math>
 
−
 
 
−
so <math>N = j(2n+j)</math>. <math>j</math> is a factor of <math>N</math>.
 
−
 
 
−
Since <math>n\geq 0</math>, it follows that <math>2n+j \geq j</math> and <math>j\leq \sqrt{N}</math>
 
−
 
 
−
Since there are exactly <math>5</math> values of <math>j</math> that satisfy the equation, there must be either <math>9</math> or <math>10</math> factors to <math>N</math>. This means <math>N=p_1^2p_2^2</math> or <math>N=p_1p_2^4</math>.
 
−
Unfortunately, we cannot simply observe prime factorizations of <math>N</math> because the factor <math>(2n+j)</math> does not cover all integers for any given value of <math>j</math>
 
  
 +
Since <math>n\geq 0</math>, it follows that <math>2n+j \geq j</math> and <math>j\leq \sqrt{N}</math>.
  
 +
Since there are exactly <math>5</math> values of <math>j</math> that satisfy the equation, there must be either <math>9</math> or <math>10</math> factors of <math>N</math>. This means <math>N=p_1^2p_2^2</math> or <math>N=p_1p_2^4</math>. Unfortunately, we cannot simply observe prime factorizations of <math>N</math> because the factor <math>(2n+j)</math> does not cover all integers for any given value of <math>j</math>.
  
 
Instead we do some casework:
 
Instead we do some casework:
  
−
<b>If <math>N</math> is odd</b>, then <math>j</math> must also be odd. For every odd value of <math>j</math>, <math>2n+j</math> is also odd, making this case valid for all odd <math>j</math>. Looking at the forms above and the bound of 1000, N must be
+
*If <math>N</math> is odd, then <math>j</math> must also be odd. For every odd value of <math>j</math>, <math>2n+j</math> is also odd, making this case valid for all odd <math>j</math>. Looking at the forms above and the bound of <math>1000</math>, <math>N</math> must be
−
 
+
<cmath>(3^2\cdot5^2),\ (3^2\cdot7^2),\ (3^4\cdot5),\ (3^4\cdot7),\ (3^4\cdot 11)</cmath>
−
<math>(3^2\cdot5^2)</math>, <math>(3^2\cdot7^2)</math>, <math>(3^4\cdot5)</math>, <math>(3^4\cdot7)</math> or <math>(3^4\cdot 11)</math>
+
:Those give <math>5</math> possibilities for odd <math>N</math>.
−
 
+
*If <math>N</math> is even, then <math>j</math> must also be even. Substituting <math>j=2k</math>, we get
−
Those give <math>5</math> possibilities for odd <math>N</math>
+
<cmath>N = 4k(n+k) \Longrightarrow \frac{N}{4} = k(n+k)</cmath>
−
 
 
−
 
 
−
<b>If <math>N</math> is even</b>, then <math>j</math> must also be even. Substituting <math>j=2k</math>, we get
 
−
 
 
−
<math>N = 4k(n+k)</math>
 
  
−
<math>\frac{N}{4} = k(n+k)</math>
+
:Now we can just look at all the [[prime factorization]]s since <math>(n+k)</math> cover the integers for any <math>k</math>. Note that our upper bound is now <math>250</math>:
  
−
Now we can just look at all the prime factorizations since <math>(n+k)</math> cover the integers for any <math>k</math>. Note that our upper bound is now 250
+
<cmath>\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)</cmath>
  
−
<math>\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),</math> or <math>(3^4\cdot2)</math>
+
: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{015}</math>
 
 
== 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}}
  
 
[[Category:Intermediate Number Theory Problems]]
 
[[Category:Intermediate Number Theory Problems]]

Revision as of 16:27, 26 April 2008

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

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

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2006_AIME_II_Problems/Problem_13&oldid=25577"