Q8 Matemática  (Middle European Mathematical Olympiad 2010)

Seja $n$ um inteiro positivo. Um quadrado $ABCD$ é particionado em quadrados unitários $n^2$. Cada um deles é dividido em dois triângulos pela diagonal paralela a $BD$. Alguns dos vértices dos quadrados unitários são coloridos de vermelho de tal forma que cada um desses triângulos $2n^2$ contém pelo menos um vértice vermelho. Encontre o menor número de vértices vermelhos. (4ª Olimpíada de Matemática da Europa Central, Competição por Equipes, Problema 4)