Turkish Mathematical Olympiad

Let $f_{(i,j)}$ be the number written on $(i,j)$ in mod $2$. We can suppose that at the $0$th step $f_{(i,j)}=1$ for all colored unit squares $(i,j)$. We prove the statement by induction with respect to $n$, the total number of colored unit squares.

If $n=1$, then after the first step $f_{(i,j)}=1$ for the only colored unit square $(i,j)$.

Suppose that the statement is proved for $n=k$ and consider the case $n=k+1$. Let us define a partial order between colored unit squares: we say that $(i,j)\le (k,l)$ if $i\le k$ and $j\le l$. Let $(p,q)$ be any maximal element with respect to this order (there is at least one maximal element). The unit square $(p,q)$ has no any influence on other colored unit squares at any step.

If we remove $(p,q)$, then by inductive hypothesis, after $N$ steps in each of remaining unit squares the number $1$ will be written. Therefore, if we do not remove $(p,q)$, after $N$ steps $f_{(i,j)}=1$ for all unit squares except possibly for $f_{(p,q)}$.

If $f_{(p,q)}=1$, it is done. Suppose that $f_{(p,q)}=0$. It means that the first $N$ steps have added $1$ to $f_{(p,q)}$ and it is changed from $1$ to $0$. Therefore, after $2N$ steps $f_{(i,j)}=1$ for all colored unit squares.