Middle European Mathematical Olympiad 2010 Problem T-4

Let $n$ be a positive integer. A square $ABCD$ is partitioned into $n^2$ unit squares. Each of them is divided into two triangles by the diagonal parallel to $BD$. Some of the vertices of the unit squares are colored red in such a way that each of these $2n^2$ triangles contains at least one red vertex. Find the least number of red vertices.