# Maximum possible number of colored cells in a 5x5 grid where no 3x3 subgrid can include more than 5 colored cells.

In a 5x5 grid, each cell can be either colored or uncolored. What is the maximum number of cells you are able to color where no 3x3 subgrid can contain more than 5 colored cells?

I can get $$18$$ colored squares: color the 2x2s in the corners and either the cell in the first row, third column and last row, third column, or third row, first column and third row, last column. I was asking for your thought process because I simply used trial and error, recognizing that the optimal cells to color tend to be those shared by the fewest 3x3 subgrids. I was wondering if there was a more methodical approach in addition to an answer for the problem.

I saw this problem posted on a display advertising a club at school. When I contacted the club leaders they did not know the solution, and so I thought I'd ask this community. This is in no way schoolwork.

• @Gary, if it helps to answer the question, the most I've been able to color is 18: color the 2x2s in the corners and either the cell in the first row, third column and last row, third column, or third row, first column and third row, last column. I was asking for your thought process because I simply used trial and error, recognizing that the optimal cells to color tend to be those shared by the fewest 3x3 subgrids. I was wondering if there was a more methodical approach in addition to an answer for the problem. Commented Sep 29, 2022 at 21:08
• @Gary in regards to your comment about this question being homework for a class, that is decidedly not the case. I saw this problem posted on a display advertising a club at school. When I contacted the club leaders they did not know the solution, and so I thought I'd ask this community. This is in no way schoolwork. Commented Sep 29, 2022 at 23:03
• Thanks for the updated. Your question has been improved significantly.
– Gary
Commented Sep 30, 2022 at 7:09

 aabbb
aabbb
ccddd
ccddd
ccddd


Assume there exists a solution with 19. There are at most 5 in the d region, at most 5 in the b, and at most 5 in the c region, hence a is completely filled with 4. So all is sharp, i.e., there are exactly 5 in each of b, c, d. Then at least one of the left two b fields and at least one of the top two c fields is coloured, giving us already 6 coloured fields in the top left $$3\times3$$, contradiction!

Yes, $$18$$ is optimal. You can solve the problem via integer linear programming as follows. For $$(r,c)\in \{1,2,3\} \times \{1,2,3\}$$, let $$S_{rc}$$ be the set of $$9$$ cells in the $$3 \times 3$$ subgrid with top-left corner $$(r,c)$$. For $$(i,j)\in\{1,\dots,5\}\times\{1,\dots,5\}$$, let binary decision variable $$x_{ij}$$ indicate whether cell $$(i,j)$$ is colored. The problem is to maximize $$\sum_{i=1}^5 \sum_{j=1}^5 x_{ij}$$ subject to linear constraints $$\sum_{(i,j)\in S_{rc}} x_{ij} \le 5 \quad \text{for (r,c)\in\{1,2,3\} \times \{1,2,3\}} \tag1\label1$$ Here is one optimal solution:

1 1 1 1 1
1 1 0 1 1
0 0 0 0 0
1 1 1 1 1
1 1 0 1 1


It turns out that the linear programming relaxation obtained by ignoring the integrality restriction also yields a maximum sum of $$18$$. The corresponding dual variables provide a short certificate of optimality. Explicitly, multiplying the upper bound constraints $$x_{ij} \le 1$$ by $$0.5$$ for the $$16$$ cells in the $$2\times 2$$ corners, multiplying the lower bound constraint $$x_{33} \ge 0$$ by $$-1$$ for the center cell, multiplying the constraints \eqref{1} by $$0.5$$ for $$(r,c)\in\{1,3\}\times\{1,3\}$$, and adding these up yields $$\sum_{i=1}^5 \sum_{j=1}^5 x_{ij} \le 18$$, as desired.

Here is an optimality proof not using any linear programming ideas. It is never disadvantageous to move a $$1$$ (coloured cell) away from the centre, so we may assume without loss of generality that the $$3×3$$ corners of optimal solutions are monotone – when going towards the centre there is never a $$0$$-to-$$1$$ transition. Now suppose a cell $$c$$ diagonally adjacent to the centre is $$0$$ (uncoloured), which by the monotonicity assumption induces three more zeros:

..bbb
.00bb
a00bb
aaa..
aaa..


But then the a- and b-regions must have at least two more zeros each, so at least $$8$$ zeros must be present, which is suboptimal given that we know a solution with only $$7$$ zeros. Hence cells like $$c$$ must be $$1$$, which induces the $$2×2$$ corners to $$1$$ by monotonicity:

11.11
11.11
.....
11.11
11.11


It is then easy to show that at most two more $$1$$s can be placed, so $$18$$ is optimal.

Maybe we can look at the squares 3x3 both on the left upper corner and the right bottom corner. Both of them need to have at least 4 white squares. If the middle square is coloured then we have at least 4+4 white cells. If it is coloured then we need to have at least 3+1+3=7 white cells. So we have at most 25-7=18 black cells: Example