Let's play a game! The game has the following rules:
Let $G$ be a $N\times N$ grid. To each grid square $(x,y)\in G$, assign either $true$ or $false$; call this mapping $C$ (that is, if $(x,y)$ is $false$, then $C(x,y)=false$). Finally, define $\omega = \|\{C(x,y)\in G| C(x,y)=true\}\|$.
Next, we have the following actions:
$$ C(x,y) = C(x+1,y+1) = true \implies C(x+1,y)=C(x,y+1):=true\\ C(x,y) = C(x+2,y) = true \implies C(x+1,y):=true\\ C(x,y) = C(x,y+2) = true \implies C(x,y+1):=true $$
That is, if two "diagonally adjacent" grid squares are both $true$, then the "orthogonally adjacent" grid squares turn $true$. Also, if two grid squares which are $true$ would be adjacent except for a $false$ grid square in between, then the "in between" grid square turns $true$.
The game ends when no further actions are possible. You win if $\forall(x,y)\in G, C(x,y)=true $.
I'm looking for the smallest $\omega$ required to win the game given $N$. I know that $\omega \leq N$, as we can define a set of grid squares $\{ (x,x) | x\in\{1,2,\dots,N\}$ that will win the game. Is this upper bound strictly equal?
Lastly, I'm tagging this as Ramsey theory because I consider $true$ and $false$ to be colorings of the grid squares. Please remove this tag if it is inappropriate.
The minimum is $\omega = N$, which is achieved by placing true along the diagonal.
Hint: Consider the perimeter of the squares marked true. Apply the Invariance Princple.