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

Solution 1:

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

Solution 2:

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.