see https://artofproblemsolving.com/community/c6h595787p3534947

This is the feedback vertex set problem in square grids. See for instance: F.R. Madelaine and I.A. Stewart, Improved upper and lower bounds on the feedback vertex numbers of grids and butterflies, Discrete Mathematics 308 (18) (2008) 4144-4164 DOI: 10.1016/j.disc.2007.08.007 http://www.sciencedirect.com/science/article/pii/S0012365X07006267

A sequence $(a_1, a_2, \cdots, a_k)$ consisting of pairwise distinct squares of a $n \times n$ chessboard is called a path if squares $a_i$ and $a_{i+1}$ share a common side for $i = 1, 2, \cdots, k_1$. Also, a subset $T$ of a chessboard is called a tree if it doesn't contain a cycle and there is a path connecting any two elements of $T$. Now, let's go back to the problem. Let $k_n$ to be the smallest number such that there is a mischievous subset $X$ of a $n\times n$ chessboard with exactly $k_n$ distinct squares. Now, let's analyse the complementary of $X$. I claim that this new subset $\overline{X}$ must be a collection of distinct trees because, if it wasn't, then there would exist a cycle in $X$, and then, there would be a cycle in the chessboard that doesn't contain any square in $X$. Now, notice that, for any tree $T$, its perimeter has a length of exactly $2|T| + 2$ units. This can be proved by induction since every time we add a square in a tree, its perimeter increase by three for the new square, but decrease by one because one side of the perimeter is used to connect this new square to the other ones. So, in total, $\overline{X}$ has a perimeter length of $2|\overline{X}| + 2t$, where $t \ge 1$ is the number of trees in $\overline{X}$. But any segment on the border of $\overline{X}$ must be on the border of $X$ or on the border of the chessboard. Since the border of the chessboard has length $4n$ and the border of $X$ has length $\le 4n$ (four sides for each square in $X$), we may conclude that: $$\text{border of }\overline{X} \le \text{border or } X + 4n \Rightarrow$$$$2|\overline{X}| + 2t \le 4|X| + 4n \Rightarrow$$$$2(n^2 - k_n) + 2 \le 4k_n + 4n \Rightarrow$$$$k_n \ge \dfrac{1}{3}n^2 - \dfrac{2}{3}n + \dfrac{1}{3}$$However, we are assuming that $Cn^2 \ge k_n$ for all $n$. Thus, $Cn^2 \ge \dfrac{1}{3}n^2 - \dfrac{2}{3}n + \dfrac{1}{3}$ for all $n$, which implies that $C \ge \dfrac{1}{3}$. In fact, $C = \dfrac{1}{3}$ works. If we choose $X$ as in the picture below, for $n = 3m$, then $|X| = 3m^2 = \dfrac{1}{3}(3m)^2$. For $n = 3m+1$, then $|X| = 3m^2 + 2m < 3m^2 + 2m + \dfrac{1}{3} = \dfrac{1}{3}(3m+1)^2$. Finally, if $n = 3m+2$, then $|X| = 3m^2 + 4m + 1 < 3m^2 + 4m + \dfrac{4}{3} = \dfrac{1}{3}(3m+2)^2$. Hence, $|X| \le \dfrac{1}{3} n^2$, which completes the proof.

Attachments:

We claim that $C \ge \frac{1}{3}$ is the answer. Firstly, we show that it is possible to find a mischievous subset of at most $\frac{1}{3}n^{2}$. Label the $(i + 1)$-th square from the left and $(j + 1)$-th square from the bottom as square $(i, j)$. Then, one possible mischievous subset is the set of all squares $(i, j)$ with $i + j \equiv 2 \pmod{3}$. We can prove that the size of this set is at most $\frac{1}{3}n^{2}$ by simple counting and casework for $n = 3k, 3k + 1$ and $n = 3k + 2$. Now, we show that the statement doesn't hold when $C < \frac{1}{3}$. To accomplish this, we claim that a mischievous subset has size at least $\frac{1}{3}(n - 1)^{2}$, which will prove the claim since the fraction of squares needed for a mischievous subset gets arbitarily close to $\frac{1}{3}$ as $n$ approaches infinity. It remains to prove that at least $\frac{1}{3}(n - 1)^{2}$ squares are neccesary. Consider each square as a vertex and an edge exist between each two neighbouring squares. When we add a vertex into a mischievous subset, remove the vertex and all edges associated with it. Let $V, E, C$ denote the number of vertices, edges and connected components of the graph. Note that removing a vertex can decrease the number of edges by at most $4$, and the total number of connected components in non-decreasing. Thus, the value $E + C - V$ will decrease by at most $3$ each time a square is added into the mischevous subset. If the subset becomes mischievous, the graph must be a forest and thus $E = V - C$ must hold, which implies $E + C - V = 0$. Initially, $E + C - V = (n - 1)^{2}$. $(V = n^{2}, E = 2n(n - 1), C = 1)$ Thus, we're done.

Can anyone motivate the solution above the weakening of condition seems to fall down from nowhere. Do you think it is difficult for a 2 problem?

Bump.....

Can you send me this question in Persia?

vjdjmathaddict wrote: Can anyone motivate the solution above the weakening of condition seems to fall down from nowhere. Do you think it is difficult for a 2 problem? Colourings for $C=\frac{1}{3}$ are obvious. So you only need to somehow estimate the lower bound for cardinality of mischievous sets. Considering graphs instead of chessboards is a very natural move. It is widely known that in any graph without cycles the number of vertices is bigger that the number of edges. If you have $m$ squares in your mischievous set, then the number of vertices $V=n^2-m$ and the number of edges $E\ge 4(n+1)(n-2)-4m$. So $V>E$ implies $n^2-m > 4(n+1)(n-2)-4m$, and the conclusion $m > n^2-\frac{4}{3}n$ follows. The rest of proof is obvious. As you can see, none step falls down from nowhere