Problem

Source: Macedonian Mathematical Olympiad 2021 P4

Tags: combinatorics



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 plus as 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. Proposed by Nikola Velov