Difference between revisions of "2002 AIME II Problems/Problem 7"
m (→Solution 2) |
|||
(8 intermediate revisions by 6 users not shown) | |||
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>. | ||
− | + | 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, 175, 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 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 == | ||
{{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}} |
Latest revision as of 12:10, 9 September 2023
Contents
Problem
It is known that, for all positive integers ,
![$1^2+2^2+3^2+\ldots+k^{2}=\frac{k(k+1)(2k+1)}6$](http://latex.artofproblemsolving.com/4/f/c/4fc69b2d25fe9c2e53533b462d9b0cce6f4ceed0.png)
Find the smallest positive integer such that
is a multiple of
.
Solution
is a multiple of
if
is a multiple of
.
So
.
Since is always odd, and only one of
and
is even, either
.
Thus, .
If , then
. If
, then
. If
, then
.
Thus, there are no restrictions on in
.
It is easy to see that only one of ,
, and
is divisible by
. So either
.
Thus, .
From the Chinese Remainder Theorem, . Thus, the smallest positive integer
is
.
Solution 2
To elaborate, we write out all 6 possibilities of pairings. For example, we have
is one pairing, and
is another. We then solve this by writing the first as and then move the 15 to get
.
We then list out all the mods of the multiples of , and realize that each of these
pairings can be generalized to become one of these multiples of
.
The chain is as follows:
and then it loops.
We see that for the first equation we have at the 24th position, so we then do
to get the first answer of 399.
Again, this is possible to repeat for all cases. CRT guarantees that we will have a solution before
or
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.