HMMT February, 2015

Solution:
The fact that $I(a, b) \subseteq (0,1)$ follows from the small-ness of $n \leq m < a+b$: the smallest solution $(u, v)$ has $0 \leq v \leq a-1$, so $u = \frac{n + b v}{a} < \frac{(a+b) + b(a-1)}{a} = b+1$ forces $1 \leq u \leq b$.

For the main part of the problem, it suffices (actually, is equivalent) to show that
(i) $0,1$ each appear exactly $n$ times as endpoints of intervals $I(a, b)$; and
(ii) each reduced rational $p/q \in (0,1)$ appears an equal (possibly zero, if $q$ is large) number of times as left and right endpoints of intervals $I(a, b)$.

We prove these separately as follows:
(i) $0$ is a (left) endpoint precisely when $v/a = 0$, or equivalently $(a, b) \in S$ has $a \mid n$ (look at $v$ mod $a$). Since $n \leq m$, we get $\phi(d)$ good pairs $(d, b) \in S$ for fixed $d \mid n$. Indeed, for any coprime residue class modulo $d$, there's exactly one representative $b$ with $b \leq m < b + d$. (Conceptually, it may be enlightening to think of $S$ as part of the Euclidean algorithm tree generated by $(1,1)$.)
Thus $0$ occurs as an endpoint $\sum_{d \mid n} \phi(d) = n$ times. Similarly, $1$ is an endpoint precisely when $u = b$, or equivalently $(a, b) \in S$ has $b \mid n$ (look at $u \bmod b$). By the same reasoning as before, we get $n$ right endpoint occurrences of $1$.

(ii) Fix $p/q \in (0,1)$ with $p, q$ coprime, so $q \geq 2$. We want to show that $v_1 / a_1 = p/q$ occurs for the same number of $(a_1, b_1) \in S$ as $u_2 / b_2 = p/q$ occurs for $(a_2, b_2) \in S$. (In fact, we will show that the number of occurrences of the former in $(x, b_1) \in S$ equals the number of the latter in $(a_2, x) \in S$.) The former occurs precisely when $1 \leq a_1 \leq m$, $q \mid a_1$, and (given the first two conditions) $v_1 \equiv p(a_1/q) \pmod{a_1}$. Given the first two conditions, the third is equivalent to $-n b_1^{-1} \equiv p(a_1/q) \pmod{a_1}$, or $b_1(a_1/q) \equiv -n p^{-1} \pmod{a_1}$. This is equivalent to having $(a_1/q) \mid n$ and $b_1 \equiv (-n/(a_1/q)) p^{-1} \pmod{q}$.

Similarly, the latter occurs precisely when $1 \leq b_2 \leq m$, $q \mid b_2$, $(b_2/q) \mid n$, and $a_2 \equiv (n/(b_2/q)) p^{-1} \pmod{q}$.

As hinted at before, if we consider the occurrences for a fixed value $x = a_1 = b_2$, then the number of permitted residue classes $b_1 \pmod{a_1} = x$ (in the former) is the same as the number of permitted residue classes $a_2 \pmod{b_2} = x$ (in the latter): $y \pmod{x}$ is permitted in the former if and only if $-y \pmod{x}$ is permitted in the latter; note that $(y, x) = 1$ if and only if $(-y, x) = 1$.