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 (→‎Solution 2)
(Significantly improved explanations, grammar, formatting, and LaTeX)
 
Line 5: Line 5:
  
 
== Solution ==
 
== Solution ==
−
<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>.  
+
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.
−
So <math>16,3,25|k(k+1)(2k+1)</math>.  
 
  
−
Since <math>2k+1</math> is always odd, and only one of <math>k</math> and <math>k+1</math> is even, either <math>k, k+1 \equiv 0 \pmod{16}</math>.  
+
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>.
  
−
Thus, <math>k \equiv 0, 15 \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>.
  
−
If <math>k \equiv 0 \pmod{3}</math>, then <math>3|k</math>. If <math>k \equiv 1 \pmod{3}</math>, then <math>3|2k+1</math>. If <math>k \equiv 2 \pmod{3}</math>, then <math>3|k+1</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>.  
  
−
Thus, there are no restrictions on <math>k</math> in <math>\pmod{3}</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.
  
−
It is easy to see that only one of <math>k</math>, <math>k+1</math>, and <math>2k+1</math> is divisible by <math>5</math>. So either <math>k, k+1, 2k+1 \equiv 0 \pmod{25}</math>.
+
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>.
−
 
 
−
Thus, <math>k \equiv 0, 24, 12 \pmod{25}</math>.
 
−
 
 
−
From the [[Chinese Remainder Theorem]], <math>k \equiv 0, 112, 224, 175, 287, 399 \pmod{400}</math>. Thus, the smallest positive integer <math>k</math> is <math>\boxed{112}</math>.
 
−
 
 
−
== Solution 2==
 
−
 
 
−
To elaborate, we write out all 6 possibilities of pairings. For example, we have
 
−
 
 
−
<math>k \equiv 24 \pmod{25}</math>
 
−
<math>k \equiv 15 \pmod{16}</math>
 
−
 
 
−
is one pairing, and
 
−
 
 
−
<math>k \equiv 24 \pmod{25}</math>
 
−
<math>k \equiv 0 \pmod{16}</math>  
 
−
 
 
−
is another. We then solve this by writing the first as <math>16k+15 \equiv 24 \pmod{25}</math> and then move the 15 to get <math>16k \equiv 9 \pmod{25}</math>.
 
−
 
 
−
We then list out all the mods of the multiples of <math>16</math>, and realize that each of these <math>6</math> pairings can be generalized to become one of these multiples of <math>16</math>.
 
−
 
 
−
The chain is as follows:
 
−
 
 
−
<math>16 \pmod{25}</math>
 
−
 
 
−
<math>7, 23, 14, 5, 21, 12, 3, 19, 10, 1, 17, 8, 24, 15, 6, 22, 13, 4, 20, 11, 27, 18, 9, 0,</math> and then it loops.
 
−
 
 
−
We see that for the first equation we have <math>9 \pmod {25}</math> 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 <math>6</math> cases. [[Chinese Remainder Theorem|CRT]] guarantees that we will have a solution before <math>25 \times 16</math> or <math>400</math> and indeed we did :P
 
  
 
== See also ==
 
== See also ==

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"