Squares of a board are shaded so any $19$x$19$ block of squares has at least $21$. At least how many squares of the board are shaded?

Question

Some squares of the $2013$ x $2013$ board are shaded so that any $19$ x $19$ block of squares has at least $21$ shaded squares. At least how many squares of the board are shaded?

Im pretty sure you’re supposed to arrange the shaded squares into diagonals with a distance of 18 squares between them because then every $19$ x $19$ square will have exactly 21 squares and with this method you will get $225123$ shaded squares or $\frac{111*2010}{2}*2+2013$

But I don’t know how to prove this is the most efficient because I know that placing shaded squares closer towards the centre are better because they are present in more $19$ x $19$ squares

Suggestions and solutions would be appreciated

Answer 1

A $(19n-1)\times (19n-1)$ board contains at least $$21n^2-22n+1$$ shaded squares.

This result is trivially true for $n=1$ so proceed inductively. Consider the original board to be in one corner of a $(19(n+1)-1)\times (19(n+1)-1)$ board. The extra squares include $2n$ 19 x 19 blocks which are disjoint apart from two of them intersecting at a single square. These must therefore contain at least $42n-1$ shaded squares. $$21n^2-22n+1+42n-1=21(n+1)^2-22(n+1)+1$$ and the result is proved.

For $n=106$ the lower bound is $$233625.$$ It is obtained by shading the squares of a 2014 x 2014 board in the method already spotted by @quarague and then deleting the two edges of the board that contain the corner "L".