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

Question

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?

Follow up: Could you explain your thought process in answering this question?

---

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.

Answer 1

 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!

Answer 2

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.

Answer 3

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.