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

(Solution 2)
(9 intermediate revisions by 7 users not shown)
Line 5: Line 5:
  
 
== Solution ==
 
== 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>.  
 
So <math>16,3,25|k(k+1)(2k+1)</math>.  
  
Line 16: Line 16:
 
Thus, there are no restrictions on <math>k</math> in <math>\pmod{3}</math>.  
 
Thus, there are no restrictions on <math>k</math> in <math>\pmod{3}</math>.  
  
Ii 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>.  
+
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>.  
  
 
Thus, <math>k \equiv 0, 24, 12 \pmod{25}</math>.  
 
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>.  
+
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 parings. 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 ==
 
{{AIME box|year=2002|n=II|num-b=6|num-a=8}}
 
{{AIME box|year=2002|n=II|num-b=6|num-a=8}}
 +
 +
[[Category: Intermediate Number Theory Problems]]
 +
{{MAA Notice}}

Revision as of 16:05, 11 August 2020

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

Solution 2

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 \pmod {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 \times 16$ or $400$ and indeed we did :P

See also

2002 AIME II (ProblemsAnswer KeyResources)
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