Every $3\times 3$ square has even number of painted cells

Question

Given a $1000\times 1000$ board. We paint some cells (at least one) so that in every $3\times 3$ square, an even number of cells are painted. What is the minimum number of painted cells?

One way to paint the cells is to paint every cell except the cells $(3k,3k)$ (assuming the cells are arranged by coordinates from $(1,1)$ to $(1000,1000)$). Every $3\times 3$ square contains exactly one such cell, so $8$ cells are painted. In total, $1000^2-333^2=889111$ cells are painted. We should be able to reduce this number.

[Source: Based on Russian competition problem]

Answer 1

On any $n\times n$ square with $n\geq 3$, the minimal number of painted cells is exactly $f(n)$, where $f(3q)=f(3q+1)=2q,f(3q+2)=2q+1$. All optimal configurations have exactly one row containing painted cells or exactly one column containing painted cells.

To see why this is true, view a painting as a map $f:[|1,n|]^2 \to {\mathbb F}_2$ (where $1$ corresponds to a painted cell and $0$ to a non-painted cell).

Consider the finite sequences $u_{1},u_{2},\ldots,u_{n-2}$ defined by

$$ u_{i}(j)=f(i,j)+f(i+1,j)+f(i+2,j) \ (1\leq j \leq n)\tag{1} $$

We call those $u$-sequences. Consider also the finite sequences $v_{1},v_{2},\ldots,v_{n-2}$ defined by

$$ v_{j}(i)=f(i,j)+f(i,j+1)+f(i,j+2) \ (1\leq i \leq n)\tag{1} $$

We call those $v$-sequences. Now, all those $u$- and $v$- sequences share the common property that the sum of three successive terms is always zero. In ${\mathbb F}_2$, such a sequence is either $0$ everywhere or three-periodic, made of two ones and one zero. It follows that if such a sequence has length $n$ then its sum (in $\mathbb N$) is either $0$, or at least $f(n)$.

If one of the $u$- or $v$-sequences is nonconstant, then the corresponding row or column must contain at least $f(n)$ painted cells and we are done.

Otherwise, all the $u$ and $v$-sequences are constant equal to $0$. Then $f$ must be three-periodic in each coordinate ($f(i,j)=f(i+3,j)=f(i,j+3)$), all the $3\times 3$ squares contain exactly four painted cells, which makes a total of $4q^2$ painted cells where $q=\lfloor \frac{n}{3} \rfloor$. This concludes the proof.

Answer 2

Haven't extensively tested this, but based on your own logic of leaving $(3k,3k)$ blank, we could paint every cell that is $3k+1,3k+1$ i.e. cells 1,4,7... and so on and $(3k,3k)$ cells. That would mean only 2 of every 9 cells are painted (I tested a limited set and it was working).

Going by the above logic the number would be $(333^2$x$2)+334+333=222445$, the final 334 and 333 owing to the final row and column open to suggestions this is my first post here, willing to learn

Answer 3

As you rightly observe, every $3\times 3$ block covers a cell of the form $(3m, 3n)$.

You can extend this observation to show that each block contains cells equivalent to $(0,0),(0,1),(0,2),(1,0), (1,1), (1,2), (2,0), (2,1), (2,2)$ modulo $3$.

You can make sure that two cells in each block are painted by choosing two of these classes and painting them. Check which ones are best on the boundaries.

However, as noted in the comments, you can do better than this, because you are allowed to have some (most) of the blocks with a count of zero painted squares.