Difference between revisions of "2013 AIME II Problems/Problem 14"
m (→The Proof) |
m (→Generalized Solution) |
||
Line 41: | Line 41: | ||
===Generalized Solution=== | ===Generalized Solution=== | ||
− | <math>Lemma:</math> Highest remainder when <math>n</math> is divided by <math>1 | + | <math>Lemma:</math> Highest remainder when <math>n</math> is divided by <math>1\leq k\leq n/2</math> is obtained for <math>k_0 = (n + (3 - n \pmod{3}))/3</math> and the remainder thus obtained is <math>(n - k_0*2) = [(n - 6)/3 + (2/3)*n \pmod{3}]</math>. |
− | <math>Note:</math> This is the second highest remainder when <math>n</math> is divided by <math>1 | + | <math>Note:</math> This is the second highest remainder when <math>n</math> is divided by <math>1\leq k\leq n</math> and the highest remainder occurs when <math>n</math> is divided by <math>k_M</math> = <math>(n+1)/2</math> for odd <math>n</math> and <math>k_M</math> = <math>(n+2)/2</math> for even <math>n</math>. |
Using the lemma above: | Using the lemma above: |
Revision as of 19:19, 19 August 2017
Contents
[hide]Problem 14
For positive integers and , let be the remainder when is divided by , and for let . Find the remainder when is divided by .
Solution
Easy solution without strict proof
We can find that
Observing these and we can find that the reminders are in groups of three continuous integers, considering this is true, and we get
So the sum is , so the answer is .
The Proof
The solution presented above does not prove why is found by dividing by . Indeed, that is the case, as rigorously shown below.
Consider the case where . We shall prove that . For all , where . This is because and . Also, as n increases, decreases. Thus, for all . Consider all and . Also, . Thus, for for .
Similar proofs apply for and . The reader should feel free to derive these proofs himself.
Generalized Solution
Highest remainder when is divided by is obtained for and the remainder thus obtained is .
This is the second highest remainder when is divided by and the highest remainder occurs when is divided by = for odd and = for even .
Using the lemma above:
So the answer is
Proof of Lemma: It is similar to stated above.
Kris17
See Also
2013 AIME II (Problems • Answer Key • Resources) | ||
Preceded by Problem 13 |
Followed by Problem 15 | |
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.