MK-MO 2021 Problem 4

For a fixed positive integer $n \geq 3$ we are given a $n$ $\times$ $n$ board with all unit squares initially white. We define a floating plusas a $5$ -tuple $(M,L,R,A,B)$ of unit squares such that $L$ is in the same row and left of $M$ , $R$ is in the same row and right of $M$ , $A$ is in the same column and above $M$ and $B$ is in the same column and below $M$ . It is possible for $M$ to form a floating plus with unit squares that are not next to it. Find the largest positive integer $k$ (depending on $n$ ) such that we can color some $k$ squares black in such a way that there is no black colored floating plus.

Authored by Nikola Velov