2006 AIME II Problem 13

Attempt Problem 13 of the 2006 AIME II below, then check your answer against the professionally curated solution from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2006 AIME II solutions, or check the answer key.

All problems are used with official legal permission of the Mathematical Association of America (MAA).

13.

How many integers NN less than 10001000 can be written as the sum of jj consecutive positive odd integers for exactly 55 values of j1?j \ge 1?

Answer: 15
Concepts:difference of squaresfactor countingparity
Difficulty rating: 3160
Small Hint:

A sum of consecutive odd numbers is a difference of squares: it equals m2k2=(mk)(m+k).m^2 - k^2 = (m - k)(m + k).

Big Hint:

So count factorizations N=abN = ab with aba \le b of equal parity: exactly five occur when NN (odd case) or N4\frac{N}{4} (even case) has 99 or 1010 divisors.

Solution:

The sum of the (k+1)(k+1)th through mmth positive odd integers is m2k2=(mk)(m+k).m^2 - k^2 = (m - k)(m + k). Writing a=mka = m - k and b=m+k,b = m + k, the representations of NN correspond exactly to the factorizations N=abN = ab with aba \le b and a,ba, b of the same parity (then m=a+b2,m = \frac{a + b}{2}, k=ba2k = \frac{b - a}{2}). So we need NN to have exactly 55 such factorizations.

If NN is odd, every divisor pair works, so NN needs 99 or 1010 divisors, i.e. N=p8,N = p^8, p9,p^9, p2q2,p^2q^2, or pq4pq^4 with p,qp, q distinct odd primes. Below 1000,1000, p8p^8 and p9p^9 are impossible, p2q2p^2 q^2 gives 225225 and 441,441, and pq4pq^4 gives 345,3^4 \cdot 5, 347,3^4 \cdot 7, 3411:3^4 \cdot 11: five odd values.

If NN is even, both factors must be even, so N=4MN = 4M and the factorizations correspond to divisor pairs of M,M, with no parity restriction; we need M<250M \lt 250 with 99 or 1010 divisors. With 99 divisors: 36,36, 100,100, 196,196, 225.225. With 1010 divisors (pq4pq^4): 324,3 \cdot 2^4, 524,5 \cdot 2^4, 724,7 \cdot 2^4, 1124,11 \cdot 2^4, 1324,13 \cdot 2^4, 234.2 \cdot 3^4. That is 4+6=104 + 6 = 10 even values, for a total of 5+10=15.5 + 10 = 15.

Problem 12#12
Full Exam

Problem 13 in Other Years