2002 AIME II Problem 7

Attempt Problem 7 of the 2002 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 2002 AIME II solutions, or check the answer key.

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

7.

It is known that, for all positive integers k,k, 12+22+32++k2=k(k+1)(2k+1)6. \begin{aligned} &1^2 + 2^2 + 3^2 + \cdots + k^2 \\ &= \frac{k(k+1)(2k+1)}{6}. \end{aligned} Find the smallest positive integer kk such that 12+22+32++k21^2 + 2^2 + 3^2 + \cdots + k^2 is a multiple of 200.200.

Answer: 112
Concepts:sum of first n squaresChinese Remainder Theoremcasework
Difficulty rating: 2500
Small Hint:

You need k(k+1)(2k+1)k(k+1)(2k+1) to be a multiple of 1200=24352,1200 = 2^4 \cdot 3 \cdot 5^2, and the factor 33 comes for free

Big Hint:

2k+12k+1 is odd, so 1616 must divide kk or k+1;k+1; separately 2525 must divide k,k, k+1,k+1, or 2k+1.2k+1. Compare the smallest solutions of the combined congruences.

Solution:

The sum is a multiple of 200200 exactly when k(k+1)(2k+1)k(k+1)(2k+1) is a multiple of 1200=24352.1200 = 2^4 \cdot 3 \cdot 5^2. The factor 33 always divides k(k+1)(2k+1)k(k+1)(2k+1) (if k1(mod3),k \equiv 1 \pmod 3, then 2k+12k+1 is divisible by 33), so only 242^4 and 525^2 matter.

Since 2k+12k+1 is odd and k,k, k+1k+1 cannot both be even, 1616 must divide kk or k+1,k+1, so k0k \equiv 0 or 15(mod16).15 \pmod{16}. Similarly 2525 must divide one of k,k, k+1,k+1, 2k+1,2k+1, giving k0,k \equiv 0, 24,24, or 12(mod25).12 \pmod{25}. Combining each pair of congruences modulo 400,400, the smallest positive solutions are 112,112, 175,175, 224,224, 287,287, 399,399, and 400.400.

The least is k=112:k = 112: indeed 112113225112 \cdot 113 \cdot 225 =(167)113(925)= (16 \cdot 7) \cdot 113 \cdot (9 \cdot 25) is a multiple of 1200.1200.

Problem 6#6
Full Exam

Problem 7 in Other Years