3. In each cell of a square table $n \times n$, we write one of the numbers $1,2, \ldots, n$ such that in each row and each column, either all numbers are the same or all are different. An example for $n=5$ is the following table

| 5 | 4 | 1 | 2 | 3 |
| :--- | :--- | :--- | :--- | :--- |
| 3 | 3 | 3 | 3 | 3 |
| 4 | 1 | 2 | 5 | 3 |
| 1 | 2 | 5 | 4 | 3 |
| 2 | 5 | 4 | 1 | 3 |

Let $S$ be the sum of all numbers in the table. How many different values of $S$ exist for a given $n$?
SOLUTION. According to the way the rows of the table are filled, we will divide all the tables under consideration into three groups:

(a) In no row of the table are there $n$ identical numbers. By summing the numbers row by row in this situation, we find that

$$
S=n(1+2+\ldots+n)=\frac{1}{2} n^{2}(n+1) .
$$

(b) In exactly one row of the table, there are $n$ identical numbers $a$. In each of the other rows, the numbers are $1,2, \ldots, n$, so $S=n a+(n-1)(1+2+\ldots+n)$ and after simplification

$$
S=n a+\frac{1}{2} n\left(n^{2}-1\right), \quad a \in\{1,2, \ldots, n\}
$$

(c) In some row of the table, there are $n$ identical numbers $b$ and in another $n$ identical numbers $c$. If $b=c$, the number $c$ appears at least twice in each column, and thus exactly $n$ times. In this case,

$$
S=n^{2} c, \quad c \in\{1,2, \ldots, n\}
$$

If $b, c$ are different numbers, there are also two different numbers in each column of the table, and thus all numbers in it are different. By summing column by column, we find that the sum $S$ has the value (5).

By substituting the given $n$ and all possible values of the numbers $a, c$ into equations (5), (6), and (7), we get a total of $2 n+1$ sums, of which $n$ sums of type (6) are mutually different and $n$ sums of type (7) are mutually different. We must therefore also investigate whether it is possible for some values of the numbers $a, c$ for the sums (5) and (6), or (5) and (7), or (6) and (7) to be equal.

In the first case, from the equation $\frac{1}{2} n^{2}(n+1)=n a+\frac{1}{2} n\left(n^{2}-1\right)$, we find that equality occurs for $a=\frac{1}{2}(n+1)$, which means only when $n$ is odd.

In the second case, we analogously conclude that (5) and (7) are equal only for $n$ odd and $c=\frac{1}{2}(n+1)$.

In the third case, we rearrange the equation $n a+\frac{1}{2} n\left(n^{2}-1\right)=n^{2} c$ to the form $2 a-1=n(2 c-n)$, from which it follows that if such two numbers $a, c \in\{1,2, \ldots, n\}$ exist, the number $n$ must be odd and the number $2 a-1$ must be a multiple of it. However, $2 a-1 \leqq 2 n-1$, so it can only be $2 a-1=n$ and $2 c-n=1$. From this, $a=\frac{1}{2}(n+1)=c$.

Summarizing all three situations, we can conclude that for $n$ even, all $2 n+1$ sums $S$ are different, whereas for $n$ odd, exactly three of these sums are the same.

Answer: The sum $S$ of all the numbers in the table takes either $2 n+1$ values (when $n$ is even) or $2 n-1$ values (when $n$ is odd).

AUXILIARY PROBLEM:

Prove that for the sum $S_{n}$ of the first $n$ natural numbers, the following holds:

$$
S_{n}=1+2+\ldots+n=\frac{1}{2} n(n+1) .
$$