2013 AIME II Problems/Problem 14
For positive integers and , let be the remainder when is divided by , and for let . Find the remainder when is divided by .
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 . By: Kris17
First, let's see what happens if we remove a restriction. Let's define as
Now, if you set as any number greater than , you get n, obviously the maximum possible. That's too much freedom; let's restrict it a bit. Hence is defined as
Now, after some thought, we find that if we set we get a remainder of , the max possible. Once we have gotten this far, it is easy to see that the original equation,
has a solution with .
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 themself.
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.
|2013 AIME II (Problems • Answer Key • Resources)|
|1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15|
|All AIME Problems and Solutions|