I was reading some problems on last years Ibero-American University Mathematics Olympiad and this one really caught my interest:
Two elements of $\mathbb Z^2$ are neighbors if their distance is $1$. The points of $\mathbb Z^2$ are colored in blue (and once colored, they remain colored) in steps according to the following rules:
- In step $n = 0$, the point $(0,0)$ is colored
- In step $n > 0$ we color all the uncolored points that have exactly $1$ colored neighbour
Determine all the elements of $\mathbb Z^2$ that will be colored after a finite number of steps $N$ in the square $[-N,N]\times [-N,N]$
I made a sketch of all the colored points after $n = 7$ steps:
The dots are the colored points.
I noticed the following: The picture is completely symmetrical, so we just need to find a pattern in the first Quadrant and then rotate the end result.
So, in the first Quadrant I colored the missing points in red and got this:
I connected them in red lines and tried to use the same pattern to predict where the other missing points will be (marked in green):
So I think that to solve this maybe instead of directly finding what points will be colored, it's easier to find what points stay uncolored. But intuition only goes so far. How can this actually be proved and formalized? My first thought was maybe to use induction on the steps but I honestly don't even know how to approach this. How can this be done?