For distinct positive integers $a, b<2012$, define $f(a, b)$ to be the number of integers $k$ with $1 \leq k<2012$ such that the remainder when $a k$ divided by 2012 is greater than that of $b k$ divided by 2012. Let $S$ be the minimum value of $f(a, b)$, where $a$ and $b$ range over all pairs of distinct positive integers less than 2012. Determine $S$.
The answer is $S=502$ (not $503!$ ).
Claim - If $\operatorname{gcd}(k, 2012)=1$, then necessarily either $k$ or $2012-k$ will counts towards $S$.

Proof. First note that both $a k, b k$ are nonzero modulo 2012. Note also that $a k \not \equiv b k$ $(\bmod 2012)$.

So if $r_{a}$ is the remainder of $a k(\bmod 2012)$, then $2012-r_{a}$ is the remainder of $a(2012-k)$ (mod 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}$.
This implies $S \geq \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 $a k \equiv b k(\bmod 2012)$ so no even $k$ counts towards $S$; and
- If $k \equiv 0(\bmod 503)$, then $a k \equiv 0(\bmod 2012)$ so no such $k$ counts towards $S$.

This gives the final answer $S \geq 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$.