Consider an $m\times n$ board where $m, n \ge 3$ are positive integers, divided into unit squares. Initially all the squares are white. What is the minimum number of squares that need to be painted red such that each $3\times 3$ square contains at least two red squares? Andrei Eckstein and Alexandru Mihalcu
Problem
Source: 2017 Romania JBMO TST 5.4
Tags: combinatorial geometry, combinatorics, Coloring
primesarespecial
22.10.2021 17:29
If not both of $m,n$ is congruent to $2$ mod $3$,we claim the answer is $2[m/3][n/3]$ and if both are $2$ mod $3$, then the minimum is $2[m/3][n/3] + min([m/3],[n/3])$. The first case is rather easy to deal with. We can obviously partition the board into $[m/3][n/3]$ $3*3$ disjoint squares and hence at least $2[m/3][n/3]$ red squares are required . We now show that these many suffice for the first case. If none of $m,n$ is $2$ mod $3$,We just paint the bottom two squares of the last column of the $3*3$ squares we just partitioned our board into.(Diagram is attached below) Clearly such a board satisfies . Now, suppose $m$ is $2$ mod $3$. Then, we just paint the rightmost two squares of the last row of the $3*3$ squares we partition into.(Diagram attached) Clearly such a board satisfies again. Now,assume both $m,n$ are $2$ mod $3$. We show that the minimum number of red squares is $2[m/3][n/3] + min([m/3],[n/3])$ We can clearly prove that atleast $3$ red squares are required for a $5*5$. Then we apply induction. Assume true for $(3a+2,3b+2)$. Assume $a \ge b$. Then we prove the assertion for $(3a+5,3b+2)$ . We just partition the board into $(3a+2)*(3b+2)$ and $3*(3b+2)$. The second part contains $b$ disjoint $3*3$s and thus by the induction hypotheses Our new board requires at least $2ab+b+2b=2(a+1)b+b$ red squares. Now, we prove the assertion for $(3a+5,3b+5)$. We partition the board into $(3a+2)*(3b+2)$ and the figure formed by the union of $(3a+2)*3, (3b+2)*3 ,3*3$(we refer to the figure as 'grid' now). Observe that we can fit in the 'grid', a figure formed by two $3*3$ squares intersecting exactly in the top right square(bottom left for the other) and $a+b$ disjoint $3*3$s. These give us at least $2a+2b+3$ more squares and by the induction hypotheses ,at least $2ab+b+2a+2b+3=2(a+1)(b+1)+b+1$ red squares are required for a $(3a+5)*(3b+5)$. Our induction is finished. Now, for the construction in this case,consider every third column and paint it like this. Skip the first square and paint the next two , then skip the next and in this manner such that the last square of the column gets painted.(Example attached) Clealry this works and we are done.
