11.58 (1) In a square consisting of $7 \times 7$ cells, mark the centers of $k$ cells such that no four of the marked points form the vertices of a rectangle with sides parallel to the grid lines. Find the maximum value of $k$.
(2) Solve the same problem for a square consisting of $13 \times 13$ cells.
[Solution] (1) Let in a $7 \times 7$ square grid, $k$ points are marked and satisfy the given conditions, where the $i$-th row has $x_{i}$ marked points. Thus, we have $x_{1}+x_{2}+\cdots+x_{7}=k$.

According to the given conditions, if two points are marked in a certain row, then in the remaining rows, no two points can be marked with the same x-coordinate. This means that the x-coordinate pairs of all the two-point groups in the same row are distinct. Since there are 7 different x-coordinates in the grid, there are a total of $C_{7}^{2}=21$ distinct x-coordinate pairs. Therefore, we have
$$
\begin{array}{l}
C_{x_{1}}^{2}+C_{x_{2}}^{2}+\cdots+C_{x_{7}}^{2} \leqslant 21, \\
x_{1}^{2}+x_{2}^{2}+\cdots+x_{7}^{2} \leqslant 42+k .
\end{array}
$$

By the Cauchy-Schwarz inequality, we have
$$
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} .
$$

From (1) and (2), we get
$$
k^{2}-7 k-7 \times 42 \leqslant 0 .
$$

Solving (3), we get $k \leqslant \frac{1}{2}(7+7 \sqrt{1+24})=21$, meaning the maximum number of points that can be marked is 21.

To achieve $k=21$, (2) must be an equality, i.e., $x_{1}=x_{2}=\cdots=x_{7}=3$. To construct an example, we use the "dictionary order method" as shown in the right figure, where exactly 21 points are marked, confirming that the maximum value of $k$ is 21.
(2) Let in a $13 \times 13$ square grid, $k$ points are marked and satisfy the given conditions. By a similar reasoning process, we get $k \leqslant 52$.

Additionally, to construct an example where $k=52$, we still use the dictionary order method. The right figure shows exactly 52 points marked and satisfying the given conditions, confirming that the maximum value of $k$ is 52.