Problem

Source:

Tags: combinatorics



A sequence $(a_1, a_2,\ldots, a_k)$ consisting of pairwise distinct squares of an $n\times n$ chessboard is called a cycle if $k\geq 4$ and squares $a_i$ and $a_{i+1}$ have a common side for all $i=1,2,\ldots, k$, where $a_{k+1}=a_1$. Subset $X$ of this chessboard's squares is mischievous if each cycle on it contains at least one square in $X$. Determine all real numbers $C$ with the following property: for each integer $n\geq 2$, on an $n\times n$ chessboard there exists a mischievous subset consisting of at most $Cn^2$ squares.