MathDB

Let

k

and

s

be positive integers such that

s<(2k + 1)^2

. Initially, one cell out of an

n \times n

grid is coloured green. On each turn, we pick some green cell

c

and colour green some

s

out of the

(2k + 1)^2

cells in the

(2k + 1) \times (2k + 1)

square centred at

c

. No cell may be coloured green twice. We say that

s

k-sparse

if there exists some positive number

C

such that, for every positive integer

n

, the total number of green cells after any number of turns is always going to be at most

Cn

. Find, in terms of

k

, the least

k

-sparse integer

s

.
[I]Proposed by Nikolai Beluhov.

Problem Statement