TITLE: Every $3\times 3$ square has even number of painted cells
QUESTION [10 upvotes]: 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]

REPLY [1 votes]: 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.
{"set_name": "stack_exchange", "score": 10, "question_id": 996863}