Difference between revisions of "2012 USAJMO Problems/Problem 5"
(→Solution 1) |
m (→Solution 1) |
||
Line 11: | Line 11: | ||
If <math>gcd(k, 2012)=1</math>, then I'll show you that <math>x_k \neq y_k</math>. This is actually pretty clear; assume that's not true and set up a congruence relation: | If <math>gcd(k, 2012)=1</math>, then I'll show you that <math>x_k \neq y_k</math>. This is actually pretty clear; assume that's not true and set up a congruence relation: | ||
<cmath>ak \equiv bk \pmod 2012</cmath> | <cmath>ak \equiv bk \pmod 2012</cmath> | ||
− | Since <math>k</math> is relatively prime to 2012, it is invertible mod 2012, so we must have <math>a \equiv b \pmod 2012</math>. Since 0 < a, b <2012<math>, this means < | + | Since <math>k</math> is relatively prime to 2012, it is invertible mod 2012, so we must have <math>a \equiv b \pmod 2012</math>. Since <math>0 < a, b <2012</math>, this means <math>a=b</math>, which the problem doesn't allow, thus contradiction, and <math>x_k \neq y_k</math>. Additionally, if <math>gcd(k, 2012)=1</math>, then <math>x_k \neq 0 \neq y_k</math>, then based on what we know about <math>n</math> from the previous paragraph, <math>n</math> is at least as large as the number of k relatively prime to 2012. Thus, <math>n \geq \phi(2012) = \phi(503*4) = 1004</math>. Thus, <math>S \geq 502</math>. |
− | To show 502 works, consider < | + | To show 502 works, consider <math>(a, b)=(1006, 2)</math>. For all even <math>k</math> we have <math>x_k=0</math>, so it doesn't count towards <math>f(1006, 2)</math>. Additionally, if <math>k = 503, 503*3</math> then <math>x_k = y_k = 1006</math>, so the only number that count towards <math>f(1006, 2)</math> 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 <math>x_k \neq 0 \neq y_k</math> and <math>2012-k</math> is also relatively prime to 2012. Since under those conditions exactly one of <math>x_k > y_k</math> and <math>x_{2012-k} > y_{2012-k}</math> is true, we have at most 1/2 of the 1004 possible k actually count to <math>f(1006, 2)</math>, so <math>\frac{1004}{2} = 502 \geq f(1006, 2) \geq S \geq 502</math>, so <math>S=502</math>. |
=== Solution 2 === | === Solution 2 === | ||
− | Let < | + | Let <math>ak \equiv r_{a} \pmod{2012}</math> and <math>bk \equiv r_{b} \pmod{2012}</math>. Notice that this means <math>a(2012 - k) \equiv 2012 - r_{a} \pmod{2012}</math> and <math>b(2012 - k) \equiv 2012 - r_{b} \pmod{2012}</math>. Thus, for every value of <math>k</math> where <math>r_{a} > r_{b}</math>, there is a value of <math>k</math> where <math>r_{b} > r_{a}</math>. Therefore, we merely have to calculate <math>\frac{1}{2}</math> times the number of values of <math>k</math> for which <math>r_{a} \neq r_{b}</math> and <math>r_{a} \neq 0</math>. |
− | However, the answer is NOT < | + | However, the answer is NOT <math>\frac{1}{2}(2012) = 1006</math>! This is because we must count the cases where the value of <math>k</math> makes <math>r_{a} = r_{b}</math> or where <math>r_{a} = 0</math>. |
Line 25: | Line 25: | ||
− | If < | + | If <math>k</math> is even, we have either <math>a \equiv 0 \pmod{1006}</math> or <math>a - b \equiv 0 \pmod{1006}</math>. So, <math>a = 1006</math> or <math>a = b + 1006</math>. We have <math>1005</math> even values of <math>k</math> (which is all the possible even values of <math>k</math>, since the two above requirements don't put any bounds on <math>k</math> at all). |
− | If < | + | If <math>k</math> is odd, if <math>k = 503</math> or <math>k = 503 \cdot 3</math>, then <math>a \equiv 0 \pmod{4}</math> or <math>a \equiv b \pmod{4}</math>. Otherwise, <math>ak \equiv 0 \pmod{2012}</math> or <math>ak \equiv bk \pmod{2012}</math>, which is impossible to satisfy, given the domain <math>a, b < 2012</math>. So, we have <math>2</math> values of <math>k</math>. |
− | In total, we have < | + | In total, we have <math>2 + 1005 = 1007</math> values of <math>k</math> which makes <math>r_{a} = r_{b}</math> or <math>r_{a} = 0</math>, so there are <math>2011 - 1007 = 1004</math> values of <math>k</math> for which <math>r_{a} \neq r_{b}</math> and <math>r_{a} \neq 0</math>. Thus, by our reasoning above, our solution is <math>\frac{1}{2} \cdot 1004 = \boxed{502}</math>. |
− | Solution by < | + | Solution by <math>\textbf{\underline{Invoker}}</math> |
=== Solution 3 === | === Solution 3 === | ||
− | The key insight in this problem is noticing that when < | + | The key insight in this problem is noticing that when <math>ak</math> is higher than <math>bk</math>, <math>a(2012-k)</math> is lower than <math> b(2012-k)</math>, except at <math>2 \pmod{4}</math> residues*. Also, they must be equal many times. <math>2012=2^2*503</math>. We should have multiples of <math>503</math>. After trying all three pairs and getting <math>503</math> as our answer, we win. But look at the <math>2\pmod{4}</math> idea. What if we just took <math>2</math> and plugged it in with <math>1006</math>? |
− | We get < | + | We get <math>502</math>. |
--[[User:Va2010|Va2010]] 11:12, 28 April 2012 (EDT)va2010 | --[[User:Va2010|Va2010]] 11:12, 28 April 2012 (EDT)va2010 | ||
=== Solution 4 === | === Solution 4 === | ||
− | Say that the problem is a race track with < | + | Say that the problem is a race track with <math>2012</math> spots. To intersect the most, we should get next to each other a lot so the negation is high. As <math>2012=2^2*503</math>, we intersect at a lot of multiples of <math>503</math>. |
==See also== | ==See also== |
Revision as of 17:20, 12 June 2019
Contents
[hide]Problem
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 .
Solutions
Solution 1
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 .
Solution 2
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 .
Solution by
Solution 3
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
Solution 4
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 .
See also
2012 USAJMO (Problems • Resources) | ||
Preceded by Problem 4 |
Followed by Problem 6 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAJMO Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.