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
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