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

Difference between revisions of "2002 AIME II Problems/Problem 7"
m (Position number was incorrect - we want the 24th multiple of 16, not the 21st)
Line 43: Line 43:
 
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.
 
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 21st position, so we then do <math>24(16)+15</math> to get the first answer of 399.
+
We see that for the first equation we have 9 mod 25 at the 24th position, so we then do <math>24(16)+15</math> 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
 
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

Revision as of 22:47, 5 March 2018

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"