NMO Selection Tests for BMO and IMO

Reduce the problem to the case where $D$ is finite, by considering an element $d_0$ of $D$, representing each residue class in $D \pmod{d_0}$ by some member of $D$, and collecting all these representatives to form a finite subset of $D$ whose greatest common divisor is again $d$.

Assume henceforth $D$ finite and induct on the cardinality of $D$. The base case $|D| = 1$ being clear, let $|D| > 1$, fix a member $a$ of $D$, notice that $D' = D \setminus \{a\}$ is non-empty since $|D| > 1$, and let $d'$ be the greatest common divisor of $D'$. Clearly, $d$ is the greatest common divisor of $a$ and $d'$, and $k = d'/d$ is integral. By the induction hypothesis, there exists a bijection $f': \mathbb{Z} \to d'\mathbb{Z}$ such that $|f'(n) - f'(n-1)|$ is a member of $D'$ for all integers $n$.

It is easily seen that every multiple of $d$ can uniquely be written in the form
$$ar + d's, \qquad (*)$$
where $r$ and $s$ are both integral and $0 \le r < k$.

Assign every integer $n$ an integer $f(n)$ in $d\mathbb{Z}$ by writing $n = kq + r$, where $q$ and $r$ are both integral and $0 \le r < k$, and letting
$$f(n) = \begin{cases} f'(q) + ar, & \text{if } q \text{ is even,} \\ f'(q) + a(k - r - 1), & \text{if } q \text{ is odd.} \end{cases}$$
This defines a function $f: \mathbb{Z} \to d\mathbb{Z}$.

Since every member of $d\mathbb{Z}$ can be written in the form $(*)$, and $f'$ is surjective, so is $f$.
Uniqueness in $(*)$ and injectivity of $f'$ imply injectivity of $f$, so $f$ is bijective.
Finally, the fact that $|f(n) - f(n-1)|$ is a member of $D$ for all integers $n$ follows from the corresponding condition for $f'$. Verifications are routine and hence omitted.