Two people in our school got 503 and I got 502. IDK I think I messed up - just casework-bashed.

Whoops they can be equal >.> Fairly sure it's 503.

I got 502, with a=4 and b=1010.

Got 502, and ran a program that agrees with me too. f(4,1010) should do the trick.

Same here! Let's hope it's 502 ... And I'm fairly sure that $f(4,1010)$ (or vice versa idk) gives you $502$. Sniped like 5 times.

what......

@Bogtro, so isn't it 502?

And $a = 4x, b = 4x + 1006$ works too!

I proved that if $|a-b|=1006$ and $a$ is a multiple of $4$, then u get 502. @fermat007 no, the vice versa won't work ill show why in a bit, gotta eat (east coast)

tells me that the answer is indeed 502. Grr...put 1005. Off by a factor of 2.

hey robin; do you know that other guy's aops account? we can ask him to run his program

I used a=1006 and b=2 to get 502 as well.

mcdonalds106_7 wrote: I proved that if $|a-b|=1006$ and $a$ is a multiple of $4$, then u get 502. @fermat007 no, the vice versa won't work ill show why in a bit, gotta eat (east coast) UGH I GOT |a-b| = 1006 and just did 1,1007

He doesn't use AoPS much. I forget his username, too.

mcdonalds106_7 wrote: I proved that if $|a-b|=1006$ and $a$ is a multiple of $4$, then u get 502. @fermat007 no, the vice versa won't work ill show why in a bit, gotta eat (east coast) Lol I know they don't I just forgot which way it went Also was it rigorous to say that "f(a,b) is minimized when f(a,b) + f(b,a)."

agh ughughugh Ioff by 1 again... apparently 502 is the answer.

CRICKET229 wrote: I used a=1006 and b=2 to get 502 as well. Huh? Urgh I thought it was strictly a - b = +/- 1006 <_<

Darn. I completely failed this one. I did a few cases and then said that it was 1005.

fermat007 wrote: CRICKET229 wrote: I used a=1006 and b=2 to get 502 as well. Huh? Urgh I thought it was strictly a - b = +/- 1006 <_< 1006 and 2 works too, you just need either $|a-b|=1006$ and $a\equiv0\pmod{4}$ or $a=1006$ and $|a-b|\equiv0\pmod{4}$.

Let \[ T(a,b) = \{1\le k <2012:ak\%2012>bk\%2012\}. \]We want to minimize $|T(a,b)|$ over all $1\le a\not = b \le 2011$. Lemma: For any integer $x$ and any integer $m$, we have \[ (2012m-x)\% 2012= \begin{cases} 2012-(x\% 2012) &\text{if } 2012\nmid x \\ 0&\text{if } 2012\mid x. \end{cases}\]Proof: Obvious. The reason for the discrepancy is that remainders upon dividing by $2012$ cannot be $2012$, they must be less! $\blacksquare$ Claim: For any $k\in [1,2011]$: If $2012\mid (a-b)k$ or $2012\mid ak$, then neither $k$ nor $2012-k$ is in $T(a,b)$. Else, exactly one of $k$ and $2012-k$ is in $T(a,b)$. Proof: Assume $2012\nmid k(a-b)$, i.e. $ak\% 2012\not = bk\% 2012$. We have \[ 2012-k\in T(a,b)\iff (2012a-ak)\% 2012 > (2012b-bk)\% 2012. \quad (\clubsuit)\]By Lemma 1: Case 1: $2012\nmid ak$. Then \begin{align*} (\clubsuit) &\iff 2012-(ak\%2012)>2012-(bk\%2012) \\ &\iff ak\% 2012\not > bk\% 2012 \\ &\iff k\not \in T(a,b), \end{align*}the last step since we assumed $ak\% 2012\not = bk\% 2012$. So in this case, $2012-k\in T(a,b) \iff k\not \in T(a,b)$, i.e. exactly one of $k$ and $2012-k$ is in $T(a,b)$. Case 2: $2012\mid ak$. Then we claim $k,2012-k\not \in T(a,b)$. This is because $ak\% 2012=0$, and $a(2012-k)\%2012=0$ too (not 2012; remainders are less than 2012!!!). $\blacksquare$ The conditions $2012\mid ka$ and $2012\mid k(a-b)$ are equivalent to $d_1\mid k$ and $d_2\mid k$ respectively, for some $d_1,d_2\mid 2012$. (In particular, $d_1=\tfrac{2012}{\gcd(2012,a)}$ and $d_2=\tfrac{2012}{\gcd(2012,a-b)}$.) So if $d_1\mid k$ or $d_2\mid k$, then neither $k$ nor $2012-k$ are in $T(a,b)$. In particular, now $d_1\mid k \iff d_1\mid 2012-k$, so in each of the following pairs (and single 1006): \[ (1,2011),(2,2010),(3,2009),\ldots,(1005,1007),(1006),\]either both are in $T(a,b)$ or exactly one is. We want to minimize $|T(a,b)|$, so we need to choose $a$ and $b$ to maximize the number of $k$ satisfying $d_1\mid k$ or $d_2\mid k$. We cannot have $d_1$ or $d_2$ be 1, since we cannot have $2012\mid a$ or $2012\mid a-b$ since $a,b\in [1,2011]$. We can have $d_2=2$ by $a-b=1006$. So if $a-b=1006$, then none of $2,4,6,\ldots,2010$ can be in $T(a,b)$, and exactly one of each of \[ (1,2011),(3,2009),\ldots,(1005,1007)\]can be in $T(a,b)$. So we have $503$ numbers in $T(a,b)$... But we still have $d_1$ to use! We should use $d_1=503$ to eliminate more than what we've already eliminated, since $2012=2^2\cdot 503$, and using $d_2=2,4$ doesn't eliminate more than we already have with $d_1$. If $d_1=503$, then we further cannot have any of $(503,3\cdot 503)$ be in $T(a,b)$. So when $d_1=503$, i.e. $\gcd(2012,a)=4$, we remove 1 more pair, which is the most we can remove (e.g. $d_1=4$ removes 0 pairs). So in fact the minimum is $\boxed{502}$ numbers in $T(a,b)$. This is achieved when, e.g. $a=1008$ and $b=2$.

v_Enhance wrote: Nice. The answer is $S = 502$ (not $503$!). Claim: If $\gcd(k, 2012) = 1$, then necessarily either $k$ or $2012-k$ will counts towards $S$. Proof. First note that both $ak$, $bk$ are nonzero modulo $2012$. Note also that $ak \not\equiv bk \pmod{2012}$. So if $r_a$ is the remainder of $ak \pmod{2012}$, then $2012-r_a$ is the remainder of $a(2012-k) \pmod{2012}$ Similarly we can consider $r_b$ and $2012-r_b$. As mentioned already, we have $r_a \neq r_b$. So either $r_a > r_b$ or $2012-r_a > 2012-r_b$. $\blacksquare$ This implies $S \ge \frac{1}{2} \varphi(2012) = 502$. But this can actually be achieved by taking $a = 4$ and $b = 1010$, since If $k$ is even, then $ak \equiv bk \pmod{2012}$ so no even $k$ counts towards $S$; and If $k \equiv 0 \pmod{503}$, then $ak \equiv 0 \pmod{2012}$ so no such $k$ counts towards $S$. This gives the final answer $S \ge 502$. Remark: A similar proof works with $2012$ replaced by any $n$ and will give an answer of $\frac{1}{2}\varphi(n)$. For composite $n$, one uses the Chinese remainder theorem to pick distinct $a$ and $b$ not divisible by $n$ such that $\operatorname{lcm}(a-b, a) = n$. This proof is incomplete. Why do you claim that $S$ will be minimum when $\gcd(k, 2012)=1$? It might be that $S$ is even smaller for some $\gcd(k, 2012)=x$, where $x$ is a positive integer greater than $1$.

Just a reminder that you're talking to Evan Chen, one of the most prestigious mathematics coaches in the world, and that his solution has been read by many people. Also, I don't really understand what you're talking about. Can you elaborate?

ChrisWren wrote: Just a reminder that you're talking to Evan Chen, one of the most prestigious mathematics coaches in the world, and that his solution has been read by many people. Also, I don't really understand what you're talking about. Can you elaborate? Um ok? I know v_Enhance is Evan Chen. The fact that $S \ge 502$ assumes that $\gcd(k, 2012)=1$. What is the proof for this assumption?

I think you misunderstood his solution. The solution states that for some $k$ relatively prime to $2012$, at least one of $k$ and $2012-k$ will be counted towards $S$.

Used the 15% hint on ARCH. Let $g(x)$ denote the remainder of $x$ mod $2012$. Define $a$ winning against $b$ at $k$ to be when $g(ak)>g(bk)$. Define them to be tying when $g(ak)=g(bk)$, and define losing similarly. The answer is $\boxed{502}$, achieved by $(a,b)=(4,1010)$. It is easy to see that $a$ and $b$ tie unless $k$ is odd. But even when $k$ is odd, $a$ loses at $k=503$ and $k=1509$ and trades wins for the other $k$(see lemma 1), giving $\dfrac{1006-2}{2}=502$. Lemma 1. If $a$ wins against $b$ at $k$ and $g(bk)\ne 0$, then $b$ wins against $a$ at $2012-k$. Proof. Trivial. Lemma 2. The number of times that $ak\equiv 0\pmod{2012}$ or $ak\equiv bk\pmod{2012}$ is maximized at(but not necessarily only at) $(a,b)=(4,1010)$. Proof. Note that the number of times is at most $\gcd(a,2012)+\gcd(a-b,2012)-2$. It is clear that $(a,b)=(4,1010)$ gives $1007$, so the only way to beat that is to have a $1006$ and something that is at least $4$. But if the other thing was a multiple of $503$, the occurrences collide and there would only be $1005$ times. If one gcd is $1006$ and the other is $4$, they collide at $k=1006$ so that case can also only give $1007$ in total, which completes our proof. We now consider when this pattern is broken, that is, when $a$ and $b$ don't trade wins at $k$ and $2012-k$. Case 1, $k=1006$. This is clearly optimal if $g(1006a)\le g(1006b)$, which is true when(but not necessarily only when) $(a,b)=(4,1010)$. Case 2, $bk\equiv 0\pmod{2012}$. This is optimal when $ak\equiv 0\pmod{2012}$ at the same $k$, which is true when(but not necessarily only when) $(a,b)=(4,1010)$. Case 3, $ak\equiv 0\pmod{2012}$ OR $ak\equiv bk\pmod{2012}$. By lemma 2, this is also maximized at(but not necessarily only at) $(a,b)=(4,1010)$. As $(a,b)=(4,1010)$ is optimal in every case, it must be optimal in total. QED.

Note that if $ka \bmod 2012 < kb \bmod 2012$, then $(2012-k)a \bmod 2012 > (2012-k)b \bmod 2012$ for $(k, 2012) = 1$. Thus, just looking at these values, we obtain a lower bound of $S \geq \frac 12 \phi(2012) = 502$. On the other hand, $502$ is achievable by picking $(4, 1010)$. Remark. [On why $503$ is incorrect] The reason is actually quite clear; the $(503, 1509)$ construction omits the $k=503$ and $k=1509$ cases, which could easily have been taken into account by just looking at the problem from the perspective of $\gcd(k, 2012) = 1$; it's essentially an overfixation of what the prime factor $2$ is doing and not that much of what $503$ is doing.

The answer is $502$. Construction: Consider $a=1010$ and $b=4$. Proof of bound: We now show that $f(a,b)\ge 502$ always. Let $r_a$ be the remainder of $ak$ mod 2012 and define $r_b$ similarly. If $r_a<r_b$ then $2012-r_b<2012-r_a$ and vise versa. Note that $ak\equiv bk\mod{2012}\iff a\equiv b\mod {2012}$ if $\gcd(k,2012)=1$, which contradcticts $1\le a\neq b<2012$. Hence for $\gcd(k,2012)=1$ of which there are $\phi(2012)=502$ many, $r_a\neq r_b$ and thus at least one if then is larger than the other, which by the previous observations shows that at least one of $r_a$ and $2012-r_a$ contributes to $S$, so $f(a,b)\ge\phi(2012)=502$, as desired.

The answer is $502$, acheived with $a = 4$ and $b = 1010$ . To see that this is maximal, note that if $ak, bk \not \equiv 0 \pmod{2012}$ then in fact $ak \pmod{2012} > bk \pmod{2012} \iff (2012 - k)a < (2012 - k)b \pmod{2012}$, and $ak$ or $bk \equiv 0 \pmod{2012}$ only if $\gcd(2012, k) \neq 1$ - this gives an upper bound of $S \ge \frac{\varphi(2012)}{2} = 502$.

We look at all possible values of $a$. We can see that when we list out the $2012$ possible remainders, every pair of values of the form $(a, b)$ sum to $2012$ except those when $ak \equiv bk \pmod{2012}$. Specifically if $ak > bk \pmod{2012}$ then $a(2012 - k) < b(2012-k) \pmod{2012}$ This is true unless $bk, ak \equiv 0 \pmod{2012}$ Thus we want to achieve $ak \equiv bk$ as much as possible. We can reduce that to $(a-b)k \equiv 0 \pmod{2012}$ We can see that $a-b < 2012$ so we obviously want $a-b = 1006$ to get the most equality cases. Remember that when we have $ak \equiv 0 \pmod{2012}$ we also have no solutions for that pair of $(2012-k, k)$ values. However, all multiples of $2$ have been used in out $a-b = 1006$ cases so we must have $k = 503, 1509$. This means that $a = 4$ or our minimal value is at $\boxed{f(4, 1010) = 502}$. $\blacksquare$

Terrible problem. Consider the $1006$ pairs given by $k=(i,2012-i)$ for $1 \le i \le 1006.$ Let $X$ be the number of $k \le 1006$ where $ak \equiv bk \pmod{2012},$ let $Y$ be the number where $bk \equiv 0$ and $ak \not\equiv 0,$ and let $Z$ be the number of pairs where $ak \equiv 0$ and $bk \not\equiv 0.$ Since for any two $k$ in a pair, the sum of $ak$ and the sum of $bk$ both are $0 \pmod{2012}$ we can see that $f(a,b)=1006-X+Y-Z.$ We also have $Y-Z$ is just the difference of the number where $bk \equiv 0$ and $ak \equiv 0$ since the other parts cancels out when subtracting. Now we want to maximize $X+Z-Y.$ We notice that the possible values for $X,Z,Y$ are $\{0,1,2,251,503\}$ by consider the gcd of $2012$ and $a,b,a-b,$ corresponding to $1,2,4,503,1006.$ We can see that if we want to have $X+Z-Y$ large we must have a $503,$ which happens when one of $a,b,a-b$ is $1006.$ Thus letting $a=1006$ we can test the options for $a-b$ to see that only $\gcd=4$ gives positive $X-Y$ which is $1$ so the minimum is $1006-503-1=502$ obtained when $a=1006,b=1002.$

I claim the answer is $502$. First, note that when at least one of $ak$, $bk$, or $ak-bk$ is $0$ mod $2012$, we have that $\gcd(2012,k)>1$. Additionally, when $\gcd(2012,k)=1$, none of $ak$, $bk$, or $ak-bk$ are $0$ mod $2012$. Therefore, for at least $\phi(2012)=1004$ values of $k$; $ak$, $bk$, and $ak-bk$ are all not $0$ mod $2012$. Using this, note that when none of $ak$, $bk$, or $ak-bk$ are $0$ mod $2012$, we have that if $R(x)$ is the remainder function of $x$ mod $2012$; \[R(ak)>R(bk) \iff R(a(2012-k))<R(b(2012-k)),\]implying that for every $k_1$ of these $1004$ values that doesn't count into $f(a,b)$, there's one unique other $k_2$ paired with it that does count into $f(a,b)$. Therefore, $S$ is at least $\frac{1004}{2}$, or $502$. Finally, this value can be achieved when $a=4$ and $b=1010$, proving that it is achievable and finishing the problem.

If $gcd(2012,k)=1 : $ First notice that $ak$ and $bk$are different and both non zero modulo $2012$. It s now easy to see that either $k$ or $2012-k$ adds a one to the sum. Thus $S \geq \frac{1}{2}\phi(2012) = 502$ and this bound can be achieved for $(a,b) = (4,1010)$ $$\mathbb{Q.E.D.}$$

The answer is $S = 502$. Let $r(x)$ denote the remainder of $x$ when $x$ is divided by $2012$. Notice that if $k$ is an integer with $1\le k < 2012$ such that $r(ak) < r(bk)$, then $r((2012-a)k) >r((2012-b)k)$ (this is false with the sole exception of when $r(ak) = 0$). This is easy to see, because $(2012-a)k\equiv -ak\pmod {2012}.$ Therefore, in order to minimize $f(a, b)$ we want $r(ak) = r(bk)$ for as many values of $k$ as possible, or $ak\equiv bk\pmod {2012}\implies k(a-b)\equiv 0\pmod {2012}$. Thus, we should have $b-a = 1006$, or $b = a+1006$. Recall that if $r(ak) < r(bk)$, $r((2012-a)k) < r((2012-b)k)$ iff $ak\equiv 0\pmod {2012}$. Therefore, we want $ak\equiv 0\pmod {2012}$ for as many values of $a$ as possible. As we also have $b = a+1006$, the ``best" we can do is for $4\mid a$ and for there to be two values of $k$ (that don't overlap with the above section) where $ak\equiv 0\pmod {2012}$ (specifically $k=503, 1509$). Taking $\boxed{a = 4, b=1010}$ does the trick, so $S=502$. $\blacksquare$

All solutions $a=1006, b\equiv 2 \pmod{4} $, or when $a=1006+b, b \equiv 2 \pmod{4}$ work