Example 3 (1) In a $4 \times 4$ grid paper, some small squares are colored red, and then two rows and two columns are crossed out. If no matter how they are crossed out, there is at least one red small square that is not crossed out, how many small squares must be colored at least?
(2) If the “$4 \times 4$” grid paper in (1) is changed to “$n \times n$” $(n \geqslant 5)$ grid paper, with other conditions unchanged, how many small squares must be colored at least?
Solution: (1) If the number of colored small squares is less than or equal to 4, then we can appropriately strike out two rows and two columns to remove all the colored small squares.

If the number of colored small squares is 5, then by the pigeonhole principle, there must be at least one row with 2 or more colored small squares. Striking out this row, the remaining number of colored small squares does not exceed 3. Then, striking out one more row and two columns can remove all the colored small squares.

If the number of colored small squares is 6, then there must be at least one row with 3 colored small squares or two rows each with 2 colored small squares. Therefore, striking out two rows can remove at least 4 colored small squares, leaving no more than 2 colored small squares. Then, striking out two columns can remove them all.
Thus, the number of colored small squares must be greater than or equal to 7.
Furthermore, if the squares are colored as shown in Figure 1, then striking out any two rows and two columns cannot remove all the colored small squares.

Therefore, at least 7 small squares must be colored.
(2) If the number of colored small squares is less than or equal to 4, then striking out two rows and two columns can definitely remove all of them.

Furthermore, if the squares are colored as shown in Figure 2, then striking out any two rows and two columns cannot remove all the colored small squares.

Therefore, at least 5 small squares must be colored.