Difference between revisions of "2002 AIME II Problems/Problem 7"

Revision as of 17:02, 16 March 2009

It is known that, for all positive integers $k$ ,

$1^2+2^2+3^2+\ldots+k^{2}=\frac{k(k+1)(2k+1)}6$ .

Find the smallest positive integer $k$ such that $1^2+2^2+3^2+\ldots+k^2$ is a multiple of $200$ .

$\frac{k(k+1)(2k+1)}{6}$ is a multiple of $200$ if $k(k+1)(2k+1)$ is a multiple of $1200 = 2^4 \cdot 3 \cdot 5^2$ . So $16,3,25|k(k+1)(2k+1)$ .

Since $2k+1$ is always odd, and only one of $k$ and $k+1$ is even, either $k, k+1 \equiv 0 \pmod{16}$ .

Thus, $k \equiv 0, 15 \pmod{16}$ .

If $k \equiv 0 \pmod{3}$ , then $3|k$ . If $k \equiv 1 \pmod{3}$ , then $3|2k+1$ . If $k \equiv 2 \pmod{3}$ , then $3|k+1$ .

Thus, there are no restrictions on $k$ in $\pmod{3}$ .

Ii is easy to see that only one of $k$ , $k+1$ , and $2k+1$ is divisible by $5$ . So either $k, k+1, 2k+1 \equiv 0 \pmod{25}$ .

Thus, $k \equiv 0, 24, 12 \pmod{25}$ .

From the Chinese Remainder Theorem, $k \equiv 0, 112, 224, 225, 287, 399 \pmod{400}$ . Thus, the smallest positive integer $k$ is $\boxed{112}$ .

@@ Line 5: / Line 5: @@
 == Solution ==
-<math>\frac{k(k+1)(2k+1)}{6}</math> is a multiple of <math>200</math> iff <math>k(k+1)(2k+1)</math> is a multiple of <math>1200 = 2^4 \cdot 3 \cdot 5^2</math>.
+<math>\frac{k(k+1)(2k+1)}{6}</math> is a multiple of <math>200</math> if <math>k(k+1)(2k+1)</math> is a multiple of <math>1200 = 2^4 \cdot 3 \cdot 5^2</math>.
 So <math>16,3,25|k(k+1)(2k+1)</math>.
@@ Line 20: / Line 20: @@
 Thus, <math>k \equiv 0, 24, 12 \pmod{25}</math>.
 From the [[Chinese Remainder Theorem]], <math>k \equiv 0, 112, 224, 225, 287, 399 \pmod{400}</math>. Thus, the smallest positive integer <math>k</math> is <math>\boxed{112}</math>.
 == See also ==
 {{AIME box|year=2002|n=II|num-b=6|num-a=8}}

2002 AIME II (Problems • Answer Key • Resources)
Preceded by Problem 6	Followed by Problem 8
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions