China Hong Kong Mathematical Olympiad

The smallest possible integer is $269$.

For $n > 1$, we rewrite the recurrence relation as follows.
$$\begin{aligned} n(a_{n+1} - a_n + 3) &= a_{n+1} + a_n + 3 \\ \Rightarrow \quad (n-1)a_{n+1} &= (n+1)a_n - 3(n-1) \\ \Rightarrow \quad \frac{a_{n+1}}{n(n+1)} &= \frac{a_n}{n(n-1)} - \frac{3}{n(n+1)} \end{aligned}$$
Let $b_n = \frac{a_n}{(n-1)n}$. This gives $b_{n+1} = b_n - \frac{3}{n(n+1)}$. Therefore, we easily obtain
$$\begin{aligned} b_n &= b_{n-1} - \frac{3}{(n-1)n} \\ &= b_{n-2} - \frac{3}{(n-2)(n-1)} - \frac{3}{(n-1)n} \\ &= \dots \\ &= b_2 - \sum_{k=2}^{n-1} \frac{3}{k(k+1)} \\ &= b_2 - 3 \sum_{k=2}^{n-1} \left( \frac{1}{k} - \frac{1}{k+1} \right) \\ &= b_2 - 3 \left( \frac{1}{2} - \frac{1}{n} \right). \end{aligned}$$
Let $a_2 = 2m + 1$. It follows that
$$a_n = (n-1)n \left( \frac{a_2}{2} - 3 \left( \frac{1}{2} - \frac{1}{n} \right) \right) = (n-1)((m-1)n + 3).$$
It is given that $2010 \mid a_{2009} = 2008(2009(m-1) + 3)$. This can be reduced to $1005 \mid 2009(m-1)+3$. As $2009 \equiv -1 \pmod{1005}$, this yields $m \equiv 4 \pmod{1005}$. Let $m = 1005t + 4$. Then
$$a_n = (n-1)((1005t+3)n + 3) = 3(n-1)((335t+1)n + 1).$$
Note that $2010 \mid a_n$ if and only if $670 \mid (n-1)((335t+1)n + 1)$. It suffices to consider odd $n$. Therefore, this becomes $670 \mid (n-1)(n+1)$.
Now, $670 = 2 \times 5 \times 67$. Therefore, $n \equiv \pm 1 \pmod{67}$. It is routine to check that $670 \div (n-1)(n+1)$ when $n = 133, 135, 267$. The next smallest possible $n$ is $n = 269$, where $670 \mid 268 \times 270$. So this is the answer.