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

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]

• Paint the squares $\{(1,k): 1 \leq k \leq 1000\} \setminus \{(1,3j-2) : 1 \leq j \leq 334 \}$ for a total of 666. – Daniel Pietrobon Oct 29 '14 at 16:05
• That means : OXXOXXOXXOXXOXX... , where X stands for a painted square. This should be the best solution. – Peter Oct 29 '14 at 16:10
• @01000100 You need to do this on rows $3,6 \dots 999$ or $2,5 \dots 998$ which gives you $666 \times 333$ – Mark Bennet Oct 29 '14 at 16:24
• @mark no, one row is sufficient. – Peter Oct 29 '14 at 16:29
• @01000100 Sorry - I see now, not every square needs a painted cell inside it. – Mark Bennet Oct 29 '14 at 16:29

## 3 Answers

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.

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 • "We paint some cells (at least one)" – JiK Oct 29 '14 at 16:41
• Sorry I will remove that part, I see the solution now could be 666, but will leave it for the original commenter to answer with that – skv Oct 29 '14 at 17:13

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.