Question 5 In a $12 \times 9$ rectangular grid, $k$ cells' centers are colored red, such that no 4 red points form the 4 vertices of a rectangle with sides parallel to the grid lines. Find the maximum value of $k$.

In a $12 \times 9$ rectangular grid, $k$ cells' centers are colored red, such that no 4 red points form the 4 vertices of a rectangle with sides parallel to the grid lines. Find the maximum value of $k$.
Solution: Let the $i$-th row of the grid be marked with $x_{i}$ red dots, then we have $x_{1}+x_{2}+\cdots+x_{12}=k$.
Similarly to the first problem, we have
$$
\mathrm{C}_{x_{1}}^{2}+\mathrm{C}_{x_{2}}^{2}+\cdots+\mathrm{C}_{x_{12}}^{2} \leqslant \mathrm{C}_{9}^{2}=36 \text {. }
$$

Simplifying and using the Cauchy-Schwarz inequality, we get
$$
k^{2}-12 k-12^{2} \times 6 \leqslant 0 \text {. }
$$

Solving this, we get $k \leqslant 36$.
This indicates that there are at most 36 red dots in the grid.
Furthermore, to construct an example with $k=36$ red dots, equality must hold in equation (2) and also in equation (1), thus we must have
$$
x_{1}=x_{2}=\cdots=x_{12}=3 \text {. }
$$

Therefore, a grid with 36 red dots can be given using either the lexicographic arrangement or the cyclic arrangement, as shown in Figure 9 and Figure 10. In summary, the maximum value of $k$ is 36.
This red dot problem can also be transformed into a "subset problem":

Write the numbers of the 9 columns as the set $S=\{1,2, \cdots, 9\}$, then the column numbers of the 3 red dots in each row correspond to a 3-element subset of $S$:
$$
\begin{array}{l}
\{1,2,3\}\{1,4,5\}\{1,6,7\}\{1,8,9\} \\
\{2,4,6\}\{2,5,8\}\{2,7,9\}\{3,4,9\} \\
\{3,5,7\}\{3,6,8\}\{4,7,8\}\{5,6,9\} ; \\
\{1,2,3\}\{4,5,6\}\{7,8,9\}\{1,4,7\} \\
\{2,5,8\}\{3,6,9\}\{1,5,9\}\{3,4,8\} \\
\{2,6,7\}\{1,6,8\}\{2,4,9\}\{3,5,7\} .
\end{array}
$$

By changing the notation, the 12 3-element subsets can be written as a $4 \times 3$ matrix:
$$
\begin{array}{l}
\{1,2,3\}\{4,7,8\}\{5,6,9\}\{1,2,3\}\{4,5,6\}\{7,8,9\} \\
\{1,4,5\}\{2,7,9\}\{3,6,8\}\{1,4,7\}\{2,5,8\}\{3,6,9\} \\
\{1,6,7\}\{2,5,8\}\{3,4,9\}\{1,5,9\}\{2,6,7\}\{3,4,8\} \\
\{1,8,9\}\{2,4,6\}\{3,5,7\} ;\{1,6,8\}\{2,4,9\}\{3,5,7\} .
\end{array}
$$

Note that in both different notations, there is a common property, that is, in the $4 \times 3$ matrix, the 3 3-element subsets in each row are mutually disjoint and their union is exactly $S$. This also provides the answer to the "9 guards on duty problem".