Found this fun puzzle:
On an infinite sheet of white graph paper (a paper with a square grid), $n$ squares are colored black. At moments $t = 1, 2, . . .$, squares are recolored according to the following rule: each square gets the color occurring at least twice in the triple formed by this square, its top neighbor, and its right neighbor.
Prove that after the moment $t = n$, all squares are white!
My solution:
I'm not sure how to make it rigorous though if anyone can help me out and it's not quite correct.
Complete induction on $n$: for all $k < n$ squares, it will be converted after $k$ steps. Let $R$ be smallest rectangle containing all black squares. Let $r$ be the bottom-row and $c$ be left-most column. By IH, $R - r$ takes $<n$ steps and $R - c$ takes $<n$ steps. Then the sum of steps is $<2n$. The last square is in bottom left at $r \cap c$, which will go with $1$ step. In total, we have $2n + 1$ steps, but I'm doubling counting because $R - c \cap R - r$. So, i'm not sure how to proceed, since we're trying to prove it will take at most $n$ steps.
I'd appreciate if someone could help with this!
I found that the problem was included in An Invitation to Discrete Mathematics, and that they give a hint which is basically a full solution. They have a similar idea to you, considering the bottom-most row and left-most column. However, you need to do a better estimate; since $R-r$ and $R-c$ are gone in at most $n-1$ steps, it follows that $(R-r)\cup (R-c)$ is also gone in at most $n-1$ steps. You do not need to add the numbers of steps, since the processes are happening at the same time. Can you take it from here?