Question 1
(1) In a $7 \times 7$ square 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$;
(2) For a $13 \times 13$ square grid, solve the same problem;
(3) For a $21 \times 21$ square grid, solve the same problem.

The first two parts of this question are from the 1975 All-Soviet Union Mathematical Olympiad, and the last part is adapted from a 1988 mathematical competition problem.
Solution: (1) Let the $i$-th row of the grid table be marked with $x_{i}$ red dots, then we have $x_{1}+x_{2}+\cdots+x_{7}=k$.

According to the given condition, if there are 2 red dots in a certain row, then in the remaining rows, there cannot be 2 red dots in the same columns as the first 2 red dots. This means that the "column pairs" of red dot pairs in the 7 rows are all different.

Since each row has 7 cells, the different column pairs of red dot pairs in 7 columns are only $C_{7}^{2}=21$. Thus, we have
$$
\begin{array}{l}
\mathrm{C}_{x_{1}}^{2}+\mathrm{C}_{x_{2}}^{2}+\cdots \mathrm{C}_{x_{7}}^{2} \leqslant 21 . \\
\left(x_{1}^{2}+x_{2}^{2}+\cdots+x_{7}^{2}\right)-\left(x_{1}+x_{2}+\cdots+x_{7}\right) \leqslant 42, \\
42+k \geqslant x_{1}^{2}+x_{2}^{2}+\cdots+x_{7}^{2} .
\end{array}
$$

For the right side of equation (1), by the Cauchy-Schwarz inequality, we have
$$
\begin{array}{l}
x_{1}^{2}+x_{2}^{2}+\cdots+x_{7}^{2} \\
\geqslant \frac{1}{7}\left(x_{1}+x_{2}+\cdots+x_{7}\right)^{2}=\frac{1}{7} k^{2} .
\end{array}
$$

Substituting equation (2) into equation (1), we get the quadratic inequality
$$
k^{2}-7 k-7 \times 42 \leqslant 0 \text {. }
$$

Solving this, we get $k \leqslant 21$.
This indicates that there are at most 21 red dots in a $7 \times 7$ grid table.
Moreover, by the lexicographic order method and the cyclic permutation method, we can respectively provide examples with 21 red dots that meet the requirements, as shown in Figure 1 and Figure 2.
In summary, the maximum value of $k$ is 21.
(2) Similarly to (1), we can derive an inequality similar to equation (3).
$$
k^{2}-13 k-13^{2} \times 12 \leqslant 0 \text {. }
$$

Solving this, we get $k \leqslant 52$.
This indicates that there are at most 52 red dots in a $13 \times 13$ grid table.
Moreover, by the lexicographic order method and the cyclic permutation method, we can respectively provide examples with 52 red dots that meet the requirements, as shown in Figure 3 and Figure 4.
In summary, the maximum value of $k$ is 52.
(3) Similarly to (1), we can derive an inequality similar to equation (3) and equation (1).
$$
k^{2}-21 k-21^{2} \times 20 \leqslant 0 \text {. }
$$

Solving this, we get $k \leqslant 105$.
This indicates that there are at most 105 red dots in a $21 \times 21$ grid table.

Moreover, as in (1) and (2), by the lexicographic order method and the cyclic permutation method, we can respectively provide examples with 105 red dots that meet the requirements, as shown in Figure 5 and Figure 6.
In summary, the maximum value of $k$ is 105.
After multiple lectures and repeated thinking about this problem, I finally came up with a good method for constructing examples using the lexicographic order method and the cyclic permutation method, and gradually realized that this series of problems is the most suitable introductory problem for teaching these two permutation methods. Furthermore, it was discovered that the red dot problem can not only be solved for the three standard cases of $7 \times 7$, $13 \times 13$, and $21 \times 21$, but also for $n \times n (n \leqslant 20)$ square grid tables, and can be reduced to the standard cases to find appropriate examples.