Question 82
A sequence $(a_{1}, a_{2}, \ldots, a_{k})$ consisting of pairwise different cells of an $n \times n$ board is called a cycle if $k \geq 4$ and cell $a_{i}$ shares a side with cell $a_{i+1}$ for every $i=1,2, \ldots, k$, where $a_{k+1}=a_{1}$. We will say that a subset $X$ of the set of cells of a board is malicious if every cycle on the board contains at least one cell belonging to $X$. Determine all real numbers $C$ with the following property: for every integer $n \geq 2$ on an $n \times n$ board there exists a malicious set containing at most $C n^{2}$ cells.