Instead of coloring, I assume that board is filled with zeros and ones. Say the number of zeros is $a$ and the number of ones is $b$. By row marking, we mark cells row-wise. By column marking we mark cells column-wise. Naturally, some cells are row and column marked at the same time. Assume to the contrary. Let there exists a filling in which $2c<min(a,b)$. Then we have $2c<a$ and $2c<b$. Let there be a cell that is both row and column marked, wlog say it is filled with 0. Since it is marked, there are less zeros on that row and on that column. Hence, if we change it to 1, then we will loose one marked cell (both in row marking and column marking) and we loose one 0 cell, and gain extra 1 cell. So the situation now is $$c'=c-1, a'=a-1, b'=b+1$$and $2c'=2c-2<a-2<a', 2c'=2c-2<b-2<b'$. Hence, we can assume that there are no points that are both row marked and column marked. This means, $c$ is the amount of row marked points plus the amount of column marked points. Notations: - $c_i^0$ be the number of zeros in $i$th column; - $r_i^0$ be the number of zeros in $i$th row; Since we can rearrange rows and columns, assume that for some $p$ and $q$ we have $$c_1^0\leq c_2^0\leq \dots c_p^0\leq n < c_{p+1}^0\leq \dots \leq c_{2n+1}^0$$$$r_1^0\leq r_2^0\leq \dots r_q^0\leq n < r_{q+1}^0\leq \dots \leq r_{2n+1}^0$$ Now let us split the board into four parts after $p$th column and $q$th row and call those parts as follows $$\begin{pmatrix} I & II \\ III & IV \end{pmatrix}$$Then it is easy to see that $I$ is made of only ones and $IV$ is made of only zeros and every cell in $II$ is marked and every cell in $III$ is marked. Now its just algebra and inequalities.