4. Determine the largest integer $n$, for which it is possible to fill a square table $n \times n$ with natural numbers from 1 to $n^{2}$ in such a way that in every $3 \times 3$ square part of it, at least one square of an integer is written.
SOLUTION. It will be easy for us to fill the $11 \times 11$ table in the required way; it is enough to choose nine out of the 11 squares of integers $1^{2}, 2^{2}, \ldots, 11^{2}$ and place them on nine cells of the table with coordinates

$$
(3,3),(3,6),(3,9), \quad(6,3),(6,6),(6,9), \quad(9,3),(9,6),(9,9)
$$

and fill the remaining cells with other numbers in any way. Since in each $3 \times 3$ part of the given table there is one of the nine mentioned cells, the number $n=11$ has the required property.

We will show that no $n \geq 12$ satisfies the problem. For any $n \geq 12$, let $k$ be the integer quotient of the number $n$ when divided by three with a remainder, so that $3 k \leq n \leq 3 k+2$ and $k \geq 4$. In the $n \times n$ table, we can then find $k^{2}$ non-overlapping (disjoint) $3 \times 3$ squares, but we have only $n$ squares of integers $1^{2}, 2^{2}, \ldots, n^{2}$ available, and it is clear that

$$
n \leq 3 k+2 < 4 k \leq k^{2}
$$

For $n \geq 12$, it is therefore impossible to fill the given table in the required way.

Answer. The largest $n$ sought is 11.

GUIDING PROBLEMS:

N1. Find all natural numbers $n$ for which it is possible to fill a square table $n \times n$ with natural numbers from 1 to $n^{2}$ such that in each row and each column there is at least one square of an integer. [It can be done for any $n$ - the squares $1^{2}, 2^{2}, \ldots, n^{2}$ can be written on the diagonal.]

N2. Determine the largest integer $n$ for which it is possible to fill a square table $n \times n$ with natural numbers from 1 to $n^{2}$ such that in each of its $2 \times 2$ square parts there is at least one square of an integer. $[n=5]$

D1. We wrote the natural numbers $1,2, \ldots, 121$ into a square table $11 \times 11$ in sequence by rows from left to right and from top to bottom. We covered exactly 16 cells with a $4 \times 4$ square tile in all possible ways. How many times was the sum of the covered numbers a square of an integer? [65-B-I-2]

D2. We will fill a square table $6 \times 6$ with all integers from 1 to 36.

a) Give an example of such a table filling where the sum of any two numbers in the same row or column is greater than 11.

b) Show that in any filling of the table, there will be two numbers in some row or column whose sum does not exceed 12. [66-C-II-2]