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?
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.

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.
