MathDB

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.

Problem Statement