Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

2002 AIME II Problems/Problem 7

Revision as of 22:47, 5 March 2018 by Tppytel (talk | contribs) (Position number was incorrect - we want the 24th multiple of 16, not the 21st)

Problem

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

Solution

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

It 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, 175, 287, 399 \pmod{400}$. Thus, the smallest positive integer $k$ is $\boxed{112}$.

Addition 9/23/17

To elaborate, we write out all 6 possibilities of parings. For example, we have

$k \equiv 24 \pmod{25}$ $k \equiv 15 \pmod{16}$

is one pairing, and

$k \equiv 24 \pmod{25}$ $k \equiv 0 \pmod{16}$

is another. We then solve this by writing the first as $16k+15 \equiv 24 \pmod{25}$ and then move the 15 to get $16k \equiv 9 \pmod{25}$.

We then list out all the mods of the multiples of 16, and realize that each of these 6 pairings can be generalized to become one of these multiples of 16.

The chain is as follows:

$16 \pmod{25}$ 7, 23, 14, 5, 21, 12, 3, 19, 10, 1, 17, 8, 24, 15, 6, 22, 13, 4, 20, 11, 27, 18, 9, 0, and then it loops.

We see that for the first equation we have 9 mod 25 at the 24th position, so we then do $24(16)+15$ to get the first answer of 399.

Again, this is possible to repeat for all 6 cases. CRT guarantees that we will have a solution before 25*16 or 400 and indeed we did :P

See also

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

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2002_AIME_II_Problems/Problem_7&oldid=92752"