49th Mathematical Olympiad in Ukraine

a) Let us enumerate all the vertices from $1$ to $2009$. Now mark those which have even numbers: $2,4,6,\dots ,2008$. This marking obviously satisfies the above condition. We'll now show that more than $1004$ vertices cannot be marked. Indeed, if we, for example, mark the first vertex, then we cannot mark vertices with numbers $2$ and $2009$. And then remaining vertices can be divided into pairs $3$-$4$, $5$-$6$, $\dots$, $2007$-$2008$ in each of which we can mark at most one vertex. Thus, the maximal number of vertices that we can mark is $1003+1=1004$.

b) Analogously to the first item, we need to mark vertices in such a way that among them there will be no three consecutive ones. Let us mark them in the following way: $1,2,4,5,7,8,\dots ,2005,2006,2008$. i.e. we don't mark vertices whose numbers are divisible by $3$ and the vertex with number $2009$. So we have $1339$ marked vertices. We'll show that we cannot mark more than $1339$ vertices. It is clear that we should mark at least two consecutive vertices, let them be $1$ and $2$. Then we clearly cannot mark vertices with numbers $3$ and $2009$. Now from each of the following triples of vertices - $4$-$6$, $7$-$9$, $2005$-$2007$ we can take at most two and also we can mark the vertex with number $2008$. So, the maximal number of vertices that we can mark is $2+2\cdot 668+1=1339$.