2012 USAJMO Problems/Problem 5
For distinct positive integers , , define to be the number of integers with such that the remainder when divided by 2012 is greater than that of divided by 2012. Let be the minimum value of , where and range over all pairs of distinct positive integers less than 2012. Determine .
First we'll show that , then we'll find an example that have .
Let be the remainder when is divided by 2012, and let be defined similarly for . First, we know that, if , then and . This implies that, since and , . Similarly, if then , establishing a one-to-one correspondence between the number of such that . Thus, if is the number of such that and , then . Now I'll show that .
If , then I'll show you that . This is actually pretty clear; assume that's not true and set up a congruence relation: Since is relatively prime to 2012, it is invertible mod 2012, so we must have . Since , this means , which the problem doesn't allow, thus contradiction, and . Additionally, if , then , then based on what we know about from the previous paragraph, is at least as large as the number of k relatively prime to 2012. Thus, . Thus, .
To show 502 works, consider . For all even we have , so it doesn't count towards . Additionally, if then , so the only number that count towards are the odd numbers not divisible by 503. There are 1004 such numbers. However, for all such odd k not divisible by 503 (so numbers relatively prime to 2012), we have and is also relatively prime to 2012. Since under those conditions exactly one of and is true, we have at most 1/2 of the 1004 possible k actually count to , so , so .
Let and . Notice that this means and . Thus, for every value of where , there is a value of where . Therefore, we merely have to calculate times the number of values of for which and .
However, the answer is NOT ! This is because we must count the cases where the value of makes or where .
So, let's start counting.
If is even, we have either or . So, or . We have even values of (which is all the possible even values of , since the two above requirements don't put any bounds on at all).
If is odd, if or , then or . Otherwise, or , which is impossible to satisfy, given the domain . So, we have values of .
In total, we have values of which makes or , so there are values of for which and . Thus, by our reasoning above, our solution is .
The key insight in this problem is noticing that when is higher than , is lower than , except at residues*. Also, they must be equal many times. . We should have multiples of . After trying all three pairs and getting as our answer, we win. But look at the idea. What if we just took and plugged it in with ? We get .
--Va2010 11:12, 28 April 2012 (EDT)va2010
Say that the problem is a race track with spots. To intersect the most, we should get next to each other a lot so the negation is high. As , we intersect at a lot of multiples of .
|2012 USAJMO (Problems • Resources)|
|1 • 2 • 3 • 4 • 5 • 6|
|All USAJMO Problems and Solutions|