HMMT November, 2024

Observe that every corner cell must be shaded, as they are the only cells incident to the four corners of the grid. Furthermore, for each side of the grid, the midpoint of that side is incident to exactly two cells; at least one must be shaded. Finally, at least one of the four central cells must be shaded to hit the central vertex of the grid.

We claim these conditions are also sufficient for a valid coloring. Let us give the points of the grid coordinates from $(0,0)$ to $(4,4)$. Then, the corner cells cover every vertex except for those of the form $(2, x)$ or $(x, 2)$ for $0 \leq x \leq 4$. Whichever cell covers $(2,0)$ must also cover $(2,1)$, and likewise the cells covering $(0,2),(2,4)$, and $(4,2)$ cover $(1,2),(2,3)$, and $(3,2)$ respectively. This leaves the center $(2,2)$, which is also covered by assumption.

Observe that for each side of the grid, of the two cells incident to its midpoint, there are 3 ways to color at least one of them. Of the 4 central cells, there are $2^{4}-1=15$ ways to color at least one. Thus, the number of colorings is $3^{4} \cdot 15=1215$.