All-Soviet-Union Mathematical Olympiad

Solution:

Notice that $0$ is good and all negative numbers are bad. Take $c = rs - r - s$. First, $c$ is bad. For suppose otherwise: $c = mr + ns$. Then $mr + ns = (s - 1)r - s$. Hence $(s - 1 - m)r = (n + 1)s$, so $r$ divides $n + 1$. Say $n + 1 = kr$, and then $s - 1 - m = ks$, so $m = (1 - k)s - 1$. But $n + 1$ is positive, so $k \geq 1$, and hence $m$ is negative. Contradiction.

If $k$ is good, then $c - k$ must be bad (otherwise $c$ would be good). Suppose $k$ is bad. Since $r$ and $s$ are relatively prime we can find integers $a$ and $b$ with $ar + bs = 1$ and hence integers $m$ and $n$ with $mr + ns = k$. Adding a multiple of $sr - rs$ to both sides if necessary, this gives a pair $m, n$ with $mr + ns = k$ and $m$ non-negative. Now take the pair with the smallest possible nonnegative $m$. Then $m \leq s - 1$ (for otherwise $m' = m - s$, $n' = n + r$ would be a pair with smaller non-negative $m$). Also $n \leq -1$, otherwise $k$ would be good. Now $c - k = (s - 1 - m)r + (-n - 1)s$ and the coefficients $s - 1 - m$ and $-n - 1$ are both non-negative, so $c - k$ is good.

So exactly $(rs - r - s + 1)/2$ integers are bad.