Thai Mathematical Olympiad

Construct a graph by representing each triangle by a vertex of a graph. Two vertices are joined by an edge if their corresponding triangles share a common side. This graph is connected and contains no cycle and hence is a tree. Since it has $n-2$ vertices, it has $n-3$ edges. Moreover, each vertex has degree at most $3$. Paint vertices black and white so that the adjacent vertices have different colors.

Let $B$ and $W$ denote the sets of black and white vertices, respectively, and let $b=|B|$, $w=|W|$. We may assume without loss of generality that $w\ge b$. Consider the set $$S=\{(x,y)\mid x\in B,y\in W\text{ and }x,y\text{ are joined by an edge}\}.$$ Then $|S|\le 3b$. On the other hand, $S$ is the set of all edges of the graph. Hence $|S|=n-3$. This implies $$b\ge \lfloor \frac{n-3}{3}\rfloor =\lfloor \frac{n}{3}\rfloor -1.$$ It follows that $$\begin{array}{rl}w-b& =(w+b)-2b\\ & \le n-2-2\left(\lfloor \frac{n}{3}\rfloor -1\right)\\ & =n-2\lfloor \frac{n}{3}\rfloor .\end{array}$$ This number can be obtained by constructing the following graph: start with a black vertex of degree one. Its adjacent vertex is white. Then draw two adjacent black vertices to the white vertex, one of which has degree $1$ and the other is adjacent to another white vertex. Repeat the construction. The terminal vertex will be slightly different depending on the remainder modulo $3$.