At the beginning, the number $a$ is on the board. The transition from $x$ to $2x+1$ or $\frac{x}{x+2}$ is referred to as a transformation. All numbers on the board are positive. 1. Variant: From the number $a$, through $k$ transformations, numbers of the form $\frac{m a + m - 1}{(2^k - m) a + 2^k - m + 1}$ with integer $0 < m < 2^k$ always arise. For all $x > 0$ it holds that: $2x + 1 > 1$, $0 < \frac{x}{x + 2} < 1$. By induction on $n$ for $n = 0, \ldots, k$, it can be shown that $a_{k-n} = \frac{2009 - b_n}{b_n}$ with $0 < b_n < 2009$ and $b_n \equiv 2^n \bmod 2009$. Thus, $a_{k-n}$ is an integer (with value 2008) if and only if $2^n \equiv 1 \bmod 2009$ or if $420 \mid n$.
Remarks: Some participants only considered specific sequences of the two transformations or tried (incorrectly) to prove that in the 4th variant, the number $a_{k-n}$ can only be an integer for $n = 0$. 2009 is not a prime number: $2009 = 7^2 \cdot 41$.