, 2024

Solution:

Assign coordinates to the cells of the grid so that the bottom-left, bottom-right, and top-right corners are $(0,0)$, $(3,0)$, and $(3,3)$ respectively.

Observe that for each quadrant of the grid, all four cells of that quadrant share a vertex. Thus, any valid coloring must have exactly one shaded cell in each quadrant. Let $A = (a_1, a_2)$, $B = (b_1, b_2)$, $C = (c_1, c_2)$, and $D = (d_1, d_2)$ denote the shaded cells in the bottom-left, bottom-right, top-left, and top-right quadrants, respectively, so that $0 \leq a_1, a_2, b_2, c_1 \leq 1$ and $2 \leq b_1, c_2, d_1, d_2 \leq 3$.

Observe that $A$ and $B$ share a vertex if and only if $|b_1 - a_1| \leq 1$ and $|b_2 - a_2| \leq 1$. The latter is always true, and the former holds precisely when $a_1 = 1$ and $b_1 = 2$. We conclude that in a valid coloring, $(a_1, b_1)$ must be one of $(0,2)$, $(0,3)$, or $(1,3)$. We can similarly deduce the same holds for $(c_1, d_1)$, $(a_2, c_2)$, and $(b_2, d_2)$.

Suppose the coordinates are chosen according to those constraints. Then, we are guaranteed the pairs of cells $(A, B)$, $(C, D)$, $(A, C)$, and $(B, D)$ do not share any vertices. The only way we get an invalid coloring is if $A$ and $D$ share a vertex, or $B$ and $C$ share a vertex.

Suppose $A$ and $D$ share a vertex. Then we must have $a_1 = a_2 = 1$ and $d_1 = d_2 = 2$, which implies $b_1 = c_2 = 3$ and $b_2 = c_1 = 0$. Thus, there is exactly one way to choose coordinates in the manner above so that $A$ and $D$ share a vertex (as depicted in the figure on the right). Likewise, there is exactly one way for $B$ and $C$ to share a vertex.

There are $3^4 = 81$ ways to choose the coordinates, so the answer is $81 - 2 = 79$.