Difference between revisions of "2006 AIME II Problems/Problem 13"

Line 24: Line 24:
  
 
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>.
 +
 +
==Solution 2==
 +
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.
  
 
== See also ==
 
== See also ==

Revision as of 01:53, 29 February 2016

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

Solution 2

It is a well known fact that the sum of the first $n$ odd positive integers is equal to $n^2$. Let $a^2$ be the sum of the odds from 1 to the integer included in the sum, and let $b^2$ 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 $j = 3$, $a^2 = 1 + 3 + 5 + 7 + 9$ and $b^2 = 1 + 3$). Then $a^2 - b^2 = 1000$, or $(a+b)(a-b) = 1000 = 2^3\cdot 5^3$. There are $4 \cdot 4 = 16$ factors of 1000, but we want all $N < 1000$, thus the answer is 15.

See also

2006 AIME II (ProblemsAnswer KeyResources)
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