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"

 
(Significantly improved explanations, grammar, formatting, and LaTeX)
 
(15 intermediate revisions by 12 users not shown)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
 +
It is known that, for all positive integers <math>k</math>,
 +
<center><math>1^2+2^2+3^2+\ldots+k^{2}=\frac{k(k+1)(2k+1)}6</math>.</center>
 +
Find the smallest positive integer <math>k</math> such that <math>1^2+2^2+3^2+\ldots+k^2</math> is a multiple of <math>200</math>.
  
 
== Solution ==
 
== Solution ==
 +
Using the given formula, we require <math>\frac{k(k+1)(2k+1)}{6}</math> to be a multiple of <math>200</math>, i.e. <math>k(k+1)(2k+1)</math> to be a multiple of <math>200 \cdot 6 = 1200 = 2^4 \cdot 3 \cdot 5^2</math>. This is equivalent to <math>k(k+1)(2k+1)</math> being divisible by each of these factors (<math>2^4 = 16</math>, <math>3</math>, and <math>5^2 = 25</math>) separately, since they are coprime.
 +
 +
Thus, for divisibility by <math>16</math>, we observe that <math>(2k+1)</math> is necessarily odd, while exactly one of <math>k</math> and <math>(k+1)</math> is even. It follows that the (at least) <math>4</math> factors of <math>2</math> must be either all contained in <math>k</math>, or all contained in <math>(k+1)</math>, yielding <math>k \equiv 0 \pmod{16}</math> or <math>k+1 \equiv 0 \pmod{16}</math> respectively. This reduces to <math>k \in \left\{0,15\right\} \pmod{16}</math>.
 +
 +
Next, if <math>k \equiv 0 \pmod{3}</math>, then obviously <math>k(k+1)(2k+1)</math> will be divisible by 3; otherwise, we will have either <math>k \equiv 1 \pmod{3}</math>, giving <math>2k+1 \equiv 2 \cdot 1 + 1 \equiv 3 \equiv 0 \pmod{3}</math>, or <math>k \equiv 2 \pmod{3}</math>, giving <math>k+1 \equiv 2+1 \equiv 3 \equiv 0 \pmod{3}</math>. Hence <math>k(k+1)(2k+1)</math> is in fact always divisible by <math>3</math>, regardless of the value of <math>k</math>.
 +
 +
Similarly, considering the cases <math>k \equiv 0,1,2,3,4 \pmod{5}</math> in turn, the residues modulo <math>5</math> of <math>k</math>, <math>(k+1)</math>, and <math>(2k+1)</math> respectively are <math>0,1,1</math>; <math>1,2,3</math>; <math>2,3,0</math>; <math>3,4,2</math>; and <math>4,0,4</math>. As <math>0</math> never appears more than once in any of these cases, we deduce that at most one of <math>k</math>, <math>(k+1)</math>, and <math>(2k+1)</math> is divisible by 5. Analogously to above, it follows that the (at least) <math>2</math> factors of <math>5</math> must be either all contained in <math>k</math>, all contained in <math>(k+1)</math>, or all contained in <math>(2k+1)</math>. These respectively give <math>k,k+1,2k+1 \equiv 0 \pmod{25}</math>, which reduces to <math>k \in \left\{0,12,24\right\} \pmod{25}</math>.
 +
 +
Accordingly, as there are <math>2</math> possible residues for <math>k</math> modulo <math>16</math> and <math>3</math> possible residues modulo <math>25</math>, we obtain a total of <math>2 \cdot 3 = 6</math> pairs of simultaneous congruences. By the [[Chinese Remainder Theorem|Chinese remainder theorem]], as <math>16</math> and <math>25</math> are coprime, each pair has a unique solution modulo <math>16 \cdot 25 = 400</math>, which we can easily calculate by simply writing out the solutions of the first congruence, then checking whether each of them also satisfies the second congruence.
 +
 +
For instance, to solve <math>k \equiv 0 \pmod{16}</math>, <math>k \equiv 12 \pmod{25}</math>, we can write out the positive multiples of <math>16</math> (to satisfy the first congruence, together with the fact that <math>k > 0</math>), then subtract <math>12</math> from each, until we find a multiple of <math>16</math> for which this subtraction gives a multiple of <math>25</math>. As it turns out, <math>16 \cdot 7 = 112</math> and <math>112-12 = 100 = 25 \cdot 4</math>, so the solution of this pair is precisely <math>k \equiv 112 \pmod{400}</math>. By applying this algorithm to each of the remaining pairs of congruences, we eventually obtain the complete solution <math>k \in \left\{0,112,175,224,287,399\right\} \pmod{400}</math>, so the smallest possible positive value of <math>k</math> is <math>\boxed{112}</math>.
  
 
== See also ==
 
== See also ==
−
* [[2002 AIME II Problems]]
+
{{AIME box|year=2002|n=II|num-b=6|num-a=8}}
 +
 
 +
[[Category: Intermediate Number Theory Problems]]
 +
{{MAA Notice}}

Latest revision as of 17:28, 16 June 2025

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

Using the given formula, we require $\frac{k(k+1)(2k+1)}{6}$ to be a multiple of $200$, i.e. $k(k+1)(2k+1)$ to be a multiple of $200 \cdot 6 = 1200 = 2^4 \cdot 3 \cdot 5^2$. This is equivalent to $k(k+1)(2k+1)$ being divisible by each of these factors ($2^4 = 16$, $3$, and $5^2 = 25$) separately, since they are coprime.

Thus, for divisibility by $16$, we observe that $(2k+1)$ is necessarily odd, while exactly one of $k$ and $(k+1)$ is even. It follows that the (at least) $4$ factors of $2$ must be either all contained in $k$, or all contained in $(k+1)$, yielding $k \equiv 0 \pmod{16}$ or $k+1 \equiv 0 \pmod{16}$ respectively. This reduces to $k \in \left\{0,15\right\} \pmod{16}$.

Next, if $k \equiv 0 \pmod{3}$, then obviously $k(k+1)(2k+1)$ will be divisible by 3; otherwise, we will have either $k \equiv 1 \pmod{3}$, giving $2k+1 \equiv 2 \cdot 1 + 1 \equiv 3 \equiv 0 \pmod{3}$, or $k \equiv 2 \pmod{3}$, giving $k+1 \equiv 2+1 \equiv 3 \equiv 0 \pmod{3}$. Hence $k(k+1)(2k+1)$ is in fact always divisible by $3$, regardless of the value of $k$.

Similarly, considering the cases $k \equiv 0,1,2,3,4 \pmod{5}$ in turn, the residues modulo $5$ of $k$, $(k+1)$, and $(2k+1)$ respectively are $0,1,1$; $1,2,3$; $2,3,0$; $3,4,2$; and $4,0,4$. As $0$ never appears more than once in any of these cases, we deduce that at most one of $k$, $(k+1)$, and $(2k+1)$ is divisible by 5. Analogously to above, it follows that the (at least) $2$ factors of $5$ must be either all contained in $k$, all contained in $(k+1)$, or all contained in $(2k+1)$. These respectively give $k,k+1,2k+1 \equiv 0 \pmod{25}$, which reduces to $k \in \left\{0,12,24\right\} \pmod{25}$.

Accordingly, as there are $2$ possible residues for $k$ modulo $16$ and $3$ possible residues modulo $25$, we obtain a total of $2 \cdot 3 = 6$ pairs of simultaneous congruences. By the Chinese remainder theorem, as $16$ and $25$ are coprime, each pair has a unique solution modulo $16 \cdot 25 = 400$, which we can easily calculate by simply writing out the solutions of the first congruence, then checking whether each of them also satisfies the second congruence.

For instance, to solve $k \equiv 0 \pmod{16}$, $k \equiv 12 \pmod{25}$, we can write out the positive multiples of $16$ (to satisfy the first congruence, together with the fact that $k > 0$), then subtract $12$ from each, until we find a multiple of $16$ for which this subtraction gives a multiple of $25$. As it turns out, $16 \cdot 7 = 112$ and $112-12 = 100 = 25 \cdot 4$, so the solution of this pair is precisely $k \equiv 112 \pmod{400}$. By applying this algorithm to each of the remaining pairs of congruences, we eventually obtain the complete solution $k \in \left\{0,112,175,224,287,399\right\} \pmod{400}$, so the smallest possible positive value of $k$ is $\boxed{112}$.

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

These problems are copyrighted © by the Mathematical Association of America, as part of the American Mathematics Competitions. AMC Logo.png

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