Problem: For distinct positive integers $a, b < 2012$,
define $f(a, b)$ to be the number of integers $k$ with $1 \le k < 2012$
such that the remainder when $ak$ divided by $2012$ is
greater than that of $bk$ 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$.

Solution: The answer is $S = 502$ (not $503$!).

\begin{claim*}
  If $\gcd(k, 2012) = 1$, then necessarily either $k$ or $2012-k$ will counts towards $S$.
\end{claim*}
\begin{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$.
\end{proof}

This implies $S \ge \half \varphi(2012) = 502$.

But this can actually be achieved by taking $a = 4$ and $b = 1010$, since
\begin{itemize}
  \ii If $k$ is even, then $ak \equiv bk \pmod{2012}$
  so no even $k$ counts towards $S$; and
  \ii If $k \equiv 0 \pmod{503}$, then $ak \equiv 0 \pmod{2012}$
  so no such $k$ counts towards $S$.
\end{itemize}
This gives the final answer $S \ge 502$.

\begin{remark*}
  A similar proof works with $2012$ replaced by any $n$
  and will give an answer of $\half\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$.
\end{remark*}