We write integers into an $n \times k$ table in such a way that every integer from 1 to $k$ appears in each of the $n$ rows. Let $S$ denote the largest of the $k$ column sums. For every $n$ and $k$, determine the smallest possible value of $S$!
Solution. From the text of the problem, $n$ and $k$ are positive integers. It is clear that for $n=1$, $S=k$, so in the following, we will assume that $n \geq 2$. In each row of the table, the sum of the numbers written is $1+2+\ldots+k=\frac{1}{2} k(k+1)$, so the sum of the numbers in the table is $\frac{1}{2} n k(k+1)$. Therefore, in some column, the sum is at least $\frac{1}{2} n(k+1)$, which means $S \geq \frac{1}{2} n(k+1)$. From this,

$$
S \geq\left\lceil\frac{1}{2} n(k+1)\right\rceil
$$

follows, considering that $S$ is an integer by definition. We will show that for $n \geq 2$, this will be the exact value of $S$. For this, we need to prove that there exists a table filling in which the sum of each column is at most

$$
\left\lceil\frac{1}{2} n(k+1)\right\rceil
$$

If $n$ is even, it is easy to find such a filling: in the odd-numbered rows, we write the integers in increasing order, and in the even-numbered rows, in decreasing order. This way, the sum of the $i$-th column is

$$
\frac{n}{2} i+\frac{n}{2}(k+1-i)=\frac{1}{2} n(k+1)
$$

If $n$ is odd (and $n \geq 3$), we can also do this: fill the first $n-3$ rows as described above (since it is an even number of rows), and thus the sum of the first $n-3$ elements in each column will be $\frac{1}{2}(n-3)(k+1)$. Therefore, to ensure that the sum in each column is at most

$$
\left\lceil\frac{1}{2} n(k+1)\right\rceil
$$

it is necessary that the sum of the last three elements in each column is at most

$$
\left\lceil\frac{1}{2} n(k+1)\right\rceil-\frac{1}{2}(n-3)(k+1)=\left\lceil\frac{1}{2} n(k+1)-\frac{1}{2}(n-3)(k+1)\right\rceil=\left\lceil\frac{3}{2}(k+1)\right\rceil
$$

This means that we need to place a $3 \times k$ table as described in the problem in the last three rows. Therefore, we will focus on the case $n=3$ in the following.

If $k=2 m+1$ is odd, i.e., $S=\frac{3(k+1)}{2}=3(m+1)$, then the table filled in the following way meets the goal:

| 1 | 2 | $\ldots$ | $i$ | $\ldots$ | $m+1$ | $m+2$ | $\ldots$ | $j$ | $\ldots$ | $2 m+1$ |
| :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| $2 m+1$ | $2 m-1$ | $\ldots$ | $2 m+3-2 i$ | $\ldots$ | 1 | $2 m$ | $\ldots$ | $4 m+4-2 j$ | $\ldots$ | 2 |
| $m+1$ | $m+2$ | $\ldots$ | $m+i$ | $\ldots$ | $2 m+1$ | 1 | $\ldots$ | $j-m-1$ | $\ldots$ | $m$ |

If $k=2 m$ is an even number and

$$
S=\left\lceil\frac{3(k+1)}{2}\right\rceil=\left\lceil\frac{6 m+3}{2}\right\rceil=3 m+2
$$

then, for example, the $3 \times k$ table can be filled as follows:

| 1 | 2 | $\ldots$ | $i$ | $\ldots$ | $m$ | $m+1$ | $\ldots$ | $j$ | $\ldots$ | $2 m$ |
| :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| $2 m$ | $2 m-2$ | $\ldots$ | $2 m+2-2 i$ | $\ldots$ | 2 | $2 m-1$ | $\ldots$ | $4 m+1-2 j$ | $\ldots$ | 1 |
| $m+1$ | $m+2$ | $\ldots$ | $m+i$ | $\ldots$ | $2 m$ | 1 | $\ldots$ | $j-m$ | $\ldots$ | $m$ |

It can be easily verified that in both tables, every row contains all integers between 1 and $k$, and no column sum exceeds $S$.