Consider an m×n board where m,n≥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×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
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≥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∗3s 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∗3s. 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.