$2n-2$

Color the first row except for one element red, the second row entirely blue, the third entirely red, and so on.

We strengthen the statement and apply induction. The strengthened statement is: Quote: There is a connected set of triangles of size $\geq 2n-2$ which touches all three sides of the grid. The base case $n=2$ is checked. For the step, delete the first row of the grid, and use the induction hypothesis to get a (WLOG blue) component $B$ in the chopped grid which touches the left and right sides, and also touches triangles in the bottom row of the original grid. If there are $\geq 2$ blue triangles in the bottom row that touch $B$ we're done. Assume there is at most one such. We will now construct a red component that will fulfill the condition. Let $\gamma$ be the path "surrounding" $B$, i.e. the shortest path composed of edges of cells that contains $B$ in its interior and so that each of each edges sits between a cell of $B$ and an element outside $B$. Let $\delta$ be the section of $\gamma$ that connects the lowest touchpoint of $B$ with the left side and the lowest touchpoint of $B$ with the right side of the grid. There are two such sections of $\gamma$, take $\delta$ to be the lower one. Now let $R$ be the set of red triangles sharing a vertex with $\delta$. Claim: $R$ is sufficient: it touches all three sides, it's connected, and it has at least $2n-2$ elements. Proof Touches all three sides: By assumption $\delta$ touches the left side of the grid, say at the vertex $P$. If $P$ isn't at the bottom side of the chopped grid then any triangle touching $P$ that's below $\delta$ is an element of $R$. If $P$ is part of the bottom side, then there are two triangles touching $P$ below $\delta$, and at most one can be blue (because there's at most one blue element in the bottom row touching $B$), so one of them is in $R$. So $R$ touches the left side, and similarly also the right. As for the bottom side, we know $\delta$ touches the bottom side of the chopped triangle, say at $Q$. There are at least 2 triangles of the bottom row touching $Q$, and similarly, at most one of them is blue, so at least one is in $R$. $R$ is connected: We'll instead prove that $R$ together with the possible blue triangle of the bottom row touching $B$ is connected. This will suffice because in any case, all vertices of that triangle are vertices of elements of $R$, so adding it doesn't influence connectedness. This set is connected because $\delta$ itself is a connected path passing through vertices of all elements of the set, and additionally each edge of $\delta$ is part of a cell in the set. $R$ has size at most $2n-2$: Again, we'll add to $R$ the possible blue triangle of the bottom row touching $B$, and now prove $|R|\leq 2n-1$. Let $Q$ be a point of $\delta$ in the bottom edge of the chopped grid. Let $k$ be the distance (in edges of the grid) from $Q$ to the left edge, and $\ell$ the distance to the right edge. So $k+\ell=n-1$. We claim each of the $k$ "right-leaning" diagonals to the left of $Q$ contains at least 2 elements of $R$. Indeed, each such diagonal must contain an edge of $\delta$. Take the bottom-most one in a certain diagonal; then the cell in the same diagonal right below it and the cell right below that are both in $R$. Similarly each "left-leaning" diagonal to the right of $Q$ contains at least two elements of $R$. Finally, directly below $Q$ there's an element of $R$ in the first row. So $$|R|\geq 2k+2\ell+1=2n-1$$which finishes the proof.